Bandit convex optimization (BCO) is a general framework for online decision making under uncertainty.  While tight regret bounds for general convex losses have been established,  existing algorithms achieving these bounds have prohibitive computational costs for high dimensional data.

In this paper, we propose a simple and practical BCO algorithm inspired by the online Newton step algorithm. We show that our algorithm achieves optimal (in terms of horizon) regret bounds for a large class of convex functions that we call $\kappa$-convex. This class contains a wide range of practically relevant loss functions including linear, quadratic, and generalized linear models. In addition to optimal regret,  this method is the most efficient known algorithm for several well-studied applications including bandit logistic regression.

Furthermore, we investigate the adaptation of our second-order bandit algorithm to online convex optimization with memory. We show that for loss functions with a certain affine structure, the extended algorithm attains optimal regret. This leads to an algorithm with optimal regret for bandit LQR/LQG problems under a fully adversarial noise model, thereby resolving an open question posed in [Gradu et al., 2020] and [Sun et al., 2023].

Finally, we show that the more general problem of BCO with (non-affine) memory is harder. We derive a  $\tilde{\Omega}(T^{2/3})$ regret lower bound, even under the assumption of smooth and quadratic losses.

Bandit Convex Optimization, Nonstochastic Control, Second Order Methods

§ INTRODUCTION

Bandit convex optimization is a prominent framework for online decision-making. At time $t$, the learner must choose an action $x_t$ from a convex constraint set $\K$. Once $x_t$ is chosen and played by the learner, the adversary reveals a convex loss function $f_t$, to which the learner suffers loss $f_t(x_t)$. Unlike full-information settings where the learner observes the loss function $f_t$ at each round, bandit feedback provides only scalar feedback—the loss associated with the chosen action, i.e., the scalar $f_t(x_t)$. The learner's goal is to minimize regret over a time horizon $T$, which is defined to be the difference between the total loss incurred by the learner and the best fixed action in $\K$ had the loss sequences were known ahead of the time:

\begin{align*}
\regret_T=\sum_{t=1}^T f_t(x_t)-\min_{x\in\K}\sum_{t=1}^T f_t(x).
\end{align*}

There is a long line of work in the online learning community that aims to attain optimal regret guarantees in bandit convex optimization, see e.g.  [Lattimore and Szepesvári, 2020]. The optimal regret for this setting in terms of the number of iterations, on the order of $O(\sqrt{T})$, was obtained in [Bubeck et al., 2017]. However, the regret of this  method has high polynomial dependence on the dimension, and similarly the running time is polynomial in both dimension and number of iterations, rendering it impractical in many applications. Motivated by the need for more efficient methods, works by [Abernethy et al., 2009, Hazan and Levy, 2014, Suggala et al., 2021] obtained more practical algorithms, but for restrictive classes of loss functions. Namely, these latter works apply to linear, strongly-convex and smooth, and quadratic losses, respectively.

One of the interesting remaining open problems in the area is to design an online algorithm that (1) works for a rich class of functions, (2) is computationally efficient, and (3) obtains $O(\sqrt{T})$ regret without heavy dependence on the dimension. We advance this research direction with an efficient second-order method with contributions summarized below.

§.§ Our contributions to bandit convex optimization

Our first contribution is a new algorithm called Bandit Newton Step (Algorithm <ref>), which is a natural adaptation of the Online Newton Step algorithm [Hazan et al., 2007] to the bandit feedback setting.  Our algorithm is an improper learning technique, i.e., it plays actions that lie outside of the constraint set $\K$, but competes with the best point inside of $\K$. Such improper learning algorithms are applicable to the applications we consider, such as online regression and online control.  The guarantees of our algorithm apply to a broad class of convex functions that we now define.

A function $f$ is called $\kappa$-convex over domain $\K \subseteq \reals^d$  iff the following holds: $f$ is convex and twice differentiable almost everywhere, and moreover $\exists c, C>0$ and a PSD matrix $0 \preceq H \preceq I$ such that the Hessian of $f$ at any $x\in\K$ satisfies

\begin{align*}
cH\preceq \nabla^2 f(x)\preceq CH \ , \ \frac{C}{c} \leq \kappa.
\end{align*}

The class of $\kappa$-convex functions generalizes loss functions encountered in prior works [Abernethy et al., 2009, Hazan and Levy, 2014, Suggala et al., 2021] and finds broad applicability in online learning. Notably, this class relaxes the requirements of strong convexity and smoothness assumptions, demanding them only along directions where the Hessian $H$ is nonzero. Consequently, it encompasses quadratic, (generalized) linear loss functions.

Contribution 1. Algorithm <ref> guarantees for the class of $\kappa$-convex loss functions:  (1) $O(d^{2.5}\sqrt{T})$ regret upper bound, and (2) per-iteration computational complexity of $O(d^2)$.

Paper     Losses     Advers.      Constraints     Regret      Running time

[Abernethy et al., 2009]      linear        $\checkmark$     $\checkmark$    $\Tilde{O}(d\sqrt{T})$
[Hazan and Levy, 2014]      strongly convex,
smooth        $\checkmark$     $\checkmark$    $\Tilde{O}(d\sqrt{T})$
[Suggala et al., 2021]      convex quadratic       $\checkmark$     $\checkmark$    $\Tilde{O}(d^{16}\sqrt{T})$     $O(d^4)$

[Bubeck et al., 2021]      bounded convex        $\checkmark$     $\checkmark$    $\Tilde{O}(d^{10.5}\sqrt{T})$     $\poly(d,T)$

[Lattimore, 2020]      convex      $\checkmark$     $\checkmark$     $\Tilde{O}(d^{2.5}\sqrt{T})$     $\exp(d, T)$

[Lattimore and Gyorgy, 2021]      convex      $\times$     $\checkmark$     $\Tilde{O}(d^{4.5}\sqrt{T})$     $\poly(d)^\dagger$

[Lattimore and György, 2023]      Lipschitz convex      $\times$     $\times$     $\Tilde{O}(d^{3/2}\sqrt{T})$     $O(d^3)$

Theorem <ref>      $\kappa$-convex     $\checkmark$      $\checkmark$   $\tilde{O}(d^{2.5}\sqrt{T})$    $O(d^{2})$

Comparison with relevant prior works that achieve $\tilde{O}(\sqrt{T})$ regret for bandit convex optimization. The last column presents the per-iteration runtime excluding projections. $\dagger$: this algorithm has $d^4$ operations that happen infrequently, thus running time over $T$ iterations is at least $\max\{d^4, T d\}$.

Next, we present the consequences of this result to some well studied settings that exhibit $\kappa$-convex losses. For these  settings, our results imply optimal in $T$ regret, and computationally efficient bandit algorithms. A detailed discussion of these contributions is provided in the Appendix <ref>.

Contribution 1.a. For bandit logistic regression, Algorithm <ref>  guarantees regret $O(d^{2.5}e^{2D} \sqrt{T})$ and running time of $O(d^2)$, where $D$ is the diameter of the domain of the linear predictor.

Contribution 1.b. For bandit linear regression, Algorithm <ref>  guarantees regret $O(d^{2.5}\sqrt{T})$ and  running time of $O(d^2)$.

§.§ Our contributions to online control

Paper     Noise     Observability      Regret

[Gradu et al., 2020]        adversarial     full     $\tilde{O}(T^{3/4})$

[Cassel and Koren, 2020]       stochastic     full      $\tilde{O}(\sqrt{T})$

[Cassel and Koren, 2020]       adversarial     full      $\tilde{O}(T^{2/3})$

[Sun et al., 2023]      semi-adversarial     partial     $\tilde{O}(\sqrt{T})$

Theorem <ref>      adversarial      partial     $\tilde{O}(\sqrt{T})$

Comparison with relevant prior works for bandit control of LQR/LQG.

Next, we proceed to studying the extension of our bandit algorithm to online control. The setting of online control is more challenging and general than bandit convex optimization, since it has a state. Very often, online control algorithms are derived from standard online learning algorithms applied to loss functions with memory. In this setting ([Anava et al., 2015]),  at each round $t$, the loss function $f_t$ depends not only on the current decision of the learner but the most recent $m$ decisions  ($m$ is often referred to as the memory length). The learner's objective is  to minimize regret, now defined as

\begin{align*}
\mregret_T=\sum_{t=m}^T f_t(x_{t-m+1},\dots,x_t)-\min_{x\in\K}\sum_{t=m}^T f_t(x,\dots,x).
\end{align*}

The reason memory is important for control is that for stable linear dynamical systems, the effect of past states and control decays exponentially over time, allowing truncation and reduction to online learning with memory.
The best known bound for bandit linear control with adversarial noise is $\tilde{O}(T^{2/3})$ [Cassel and Koren, 2020]. The work of [Sun et al., 2023] gave a $O(\sqrt{T})$ regret bound, but under a more restrictive noise model, called semi-adversarial noise. It remained an open problem to resolve the optimal rates for bandit linear control and BCO-M in general.

We address this question, and give new tight upper and lower bounds for these settings as follows.

Contribution 2. For bandit linear control problems, we propose an efficient algorithm that achieves $\tilde{O}(\sqrt{T})$ regret against fully adversarial noise model.

This upper bound leverages the special memory structure, called affine memory, in linear control problems. To see the significance of the affine memory structure, we give a tight lower bound for BCO with general memory, as per below.

Contribution 3. BCO-M with general quadratic and smooth loss functions has a $\tilde{\Omega}(T^{2/3})$ regret lower bound even when some degree of improper learning is allowed.

Our analysis establishes a clear distinction between the complexities of bandit linear control and BCO-M, indicating that structural properties of linear control problems are crucial for obtaining optimal regret bounds.

§.§ Related works

We group and survey the related works by topic.

Bandit convex optimization.

The setting of BCO is the limited (zero-order) analogue of online convex optimization, see [Hazan, 2022, Lattimore and Szepesvári, 2020] for an in-depth treatment of OCO, BCO, and other bandit settings. The first BCO algorithms for adversarial losses were gradient based [Flaxman et al., 2004], and generally applicable, but did not attain the optimal regret bound. A flurry of research followed with more general and efficient methods, culminating in an optimal regret bound and polynomial time algorithm [Bubeck et al., 2021]. That still is not the end of the picture, as the regret bounds and running time for the latter algorithm have a large (polynomial) dependence on the dimension.

Special cases of loss functions were addressed in a sequence of works. Notable in these is the optimal regret algorithm for bandit linear optimization [Abernethy et al., 2009], which is the most important subcase. Further generalizations with improved runtimes and/or regret bounds include strongly convex + smooth [Hazan and Levy, 2014], and quadratic losses [Suggala et al., 2021]. Another important research theme explores efficient bandit algorithms for stochastic losses. The second-order method of Lattimore and György, 2023 is the most relevant to our work; it develops a bandit Newton approach for minimizing Lipschitz convex losses over $\RBB^d$.

Online control. Online nonstochastic control considers the problem of controlling a discrete-time linear dynamical system with an adversarially chosen perturbation and cost sequence. The goal is to compete with the best fixed policy in some benchmark policy class. [Agarwal et al., 2019] is the first work that leverages the stability assumption on the system and proved reduction from nonstochastic control to online learning with memory, where the latter was studied in [Anava et al., 2015]. The line of work is too extensive to include here, and we refer those who are interested to Hazan and Singh, 2022 for a survey. The most relevant works to ours are perhaps Cassel and Koren, 2020, Gradu et al., 2020, Sun et al., 2023, where the authors also studied nonstochastic control. A comparison of results is included in Table <ref>.

There are two other relevant works in the full information setting [Simchowitz et al., 2020, Simchowitz, 2020]. [Simchowitz et al., 2020] proposed the state-of-art benchmark policy class of disturbance response controllers (DRCs), which both [Sun et al., 2023] and we use as the benchmark policy class for regret evaluation. [Simchowitz, 2020] leveraged the special structure of control loss and studied the subclass of OCO-M with memory problem which they referred to as OCO with Affine Memory (OCO-AM). This insight is crucial to our analysis.

Lower bounds for bandit algorithms.

Bandit convex optimization is strictly harder than OCO, and therefore in general the regret is lower bounded by $\Omega(\sqrt{T})$. [Shamir, 2013] showed a tight $\Omega(\sqrt{T})$ lower bound on the regret that holds even for strongly convex and smooth loss functions.

Bandit convex optimization with memory is harder than BCO.  [Dekel et al., 2014, Koren et al., 2017] showed a $\tilde{\Omega}(T^{2/3})$-lower bound for multi-armed bandit problems with switching/moving cost. The addition of a switching cost is a form of loss function with memory and therefore inspires the question that whether bandit optimization with memory over continuous and convex decision set with natural loss functions exhibits the same restriction. We answer this question by showing $\tilde{\Omega}(T^{2/3})$ regret lower bound for quadratic and smooth loss that is adaptive at time $t$ to the algorithm's decisions up to time $t-m$, where $m$ is the memory length. We emphasize that most if not all existing upper bound analysis for BCO and BCO-M holds for such adaptivity assumption. Table <ref> includes a summary of results in regret lower bounds for bandit algorithms.

Paper     Decision set       Regret      Note

[Dekel et al., 2014]       discrete     $\tilde{\Omega}(T^{2/3})$      $0$-$1$ moving cost

[Koren et al., 2017]       discrete     $\tilde{\Omega}(T^{2/3})$       metric moving cost

[Cesa-Bianchi et al., 2013]      continuous      $\Omega(T^{2/3})$        $0$-$1$ moving cost

Theorem <ref>      continuous      $\tilde{\Omega}(T^{2/3})$     smooth, quadratic loss with memory

Comparison with relevant prior works on lower bounds for bandit algorithms.

§.§ Paper organization

In the next section we detail applications of our bandit algorithm to online learning. Following that, in Section <ref> we give details of the setting and notations considered. In Section <ref> we give the simplest version of Bandit Newton Step (BNS) and main theorem statement. Following that we give the extension of BNS to the OCO with affine memory setting in Section <ref>. Lower bounds for OCO with memory are given in Section <ref>. Details of the application to control and proof details are left to the appendix.

§ PRELIMINARIES

We divide the preliminaries for three topics: BCO (used in Section <ref>), BCO with memory (BCO-M, used in Section <ref> and Section <ref>), and control of LQR/LQG (used in Section <ref>).

§.§ BCO

We consider the bandit convex optimization problem over a convex and compact set $\K \subset \mathbb{R}^d$. At each round, the learner is allowed to play a point $y_t\in\mathbb{R}^d$, after which a loss $f_t(y_t)\in\mathbb{R}$ is revealed to the learner. If $y_t$ is restricted to lie in $\K$, then the learner is called a proper learner. If $y_t$ can lie outside $\K$, then the learner is called improper. In this work, we provide an improper learning algorithm for $\kappa$-convex losses. The performance of the learner is measured by regret, i.e. the difference between the loss incurred by the learner and the best single point $x^*\in\K$ had the loss functions were known ahead of the time, i.e.

\begin{align*}
\regret_T=\sum_{t=1}^T f_t(y_t) - \min_{x^* \in \K} \sum_{t=1}^T f_t(x^*) .
\end{align*}

We make the following assumptions on the sequence of loss functions $\{f_t\}_{t=1}^T$:
[Oblivious Adversary]

The sequence of losses $\{f_t\}_{t=1}^T$ are fixed ahead of the game.

[$\kappa$-convex losses]

The sequence of losses $\{f_t\}_{t=1}^T$ are $\kappa$-convex. That is, $\exists c, C > 0,$ and PSD matrices $0 \preceq H_t \preceq I$ such that

\[
\forall x \in \K+\ball, \  t\in [T], \quad cH_t\preceq \nabla^2 f_t(x)\preceq CH_t \ , \ \text{where } \frac{C}{c} \leq \kappa.
\]

[Bounded range and gradients]

$\exists B, L> 0$ such that
$\{f_t\}_{t=1}^T$ satisfies

\begin{align*}
\max_{1\le t\le T}\sup_{x\in\K} f_t(x)\le B, \ \ \ \max_{1\le t\le T}\sup_{x\in\K} \|\nabla f_t(x)\|_2\le L.
\end{align*}

§.§ Control of LQR/LQG

An important application of BCO-M is its reduction from nonstochastic LQR/LQG control. Consider the following partially observable linear dynamical system governed by dynamics $(A, B)$ and observation matrix $C$:

\begin{align*}
\x_{t+1}=A\x_t+B\uv_t+\w_t, \ \ \ \y_t=C\x_t+\e_t,
\end{align*}

where $\x_t, \uv_t$ are the state and control played at time $t$, respectively. $\w_t$ is the perturbation at time $t$. The system's state is not directly accessible. Instead, an observation, $\y_t$, which is usually a noisy low-dimension projection of the state $\x_t$, is accessible. $\e_t$ is the observation noise. $A,B,C$ are of appropriate dimensions, i.e. $A\in\mathbb{R}^{d_{\x}\times d_{\x}}$ $B\in\mathbb{R}^{d_{\x}\times d_{\uv}}$, and $C\in\mathbb{R}^{d_{\y}\times d_{\x}}$, where $d_{\x},d_{\y},d_{\uv}$ are the dimensions of $\x_t,\y_t,\uv_t$. $\w_t\in\mathbb{R}^{d_{\x}}$, and $\e_t\in\mathbb{R}^{d_{\y}}$.
In addition, we assume the system has bounded dynamics and permits a strongly stable linear policy:
[Strongly stabilizable with bounded dynamics]

The matrices that govern the system dynamics and observations are bounded: $\|A\|_{\mathrm{op}}\le \kappa_A$,  $\|B\|_{\mathrm{op}}\le \kappa_B$,  $\|C\|_{\mathrm{op}}\le \kappa_C$, and $\exists K\in\mathbb{R}^{d_{\uv}\times d_{\y}}$ with $A+BKC=HLH^{-1}$ for some $H\succ 0$ and $\max\{\|K\|, \|H\|\|H^{-1}\|\}\le \kappa$, $\|L\|\le 1-\gamma$ for some $\kappa>0$, $0<\gamma \le 1$.

In the nonstochastic control setting, we make no distributional assumption on the perturbation and noise sequence $\{\w_t, \e_t\}_{t=1}^T$, other than that they are bounded, i.e.

\begin{align*}
\max_{t\in[T]}\{\max\{\|\w_t\|_2,\|\e_t\|_2\}\}\le R_{\w,\e}.
\end{align*}

Moreover, at time $t$, after a control $\uv_t$ is played by the learner, a time-varying quadratic cost

$$c_t(\y_t, \uv_t)=\y_t^{\top} Q_t\y_t+\uv_t^{\top}R_t\uv_t$$

is revealed to the learner. We make the following assumption on the adversary.
[Oblivious adversary]

The adversary that chooses the cost and perturbation sequences is oblivious (i.e. these sequences are chosen independently of the learner's choice of controls).

Similar to [Simchowitz, 2020, Sun et al., 2023], we make strong convexity assumption on $c_t$:
[Strongly convex and smooth quadratic cost]

$\exists \alpha,\beta>0$ such that $Q_t, R_t\succeq \alpha I$ and $Q_t, R_t\preceq \beta I$.

In the bandit setting with partially observable systems, the learner only has access to the scalar loss $c_t(\y_t,\uv_t)$ in addition to the observation $\y_t$ at time $t$.
The performance in nonstochastic control is to minimize regret, defined by the total cost incurred by the learner $\A$ over a time horizon $T$ and the would-be cost incurred by the best policy in a benchmark policy class $\Pi$, had the costs been known ahead of the game, i.e.

\begin{align*}
\cregret_T(\A)=\sum_{t=1}^T c_t(\y_t^{\A}, \uv_t^{\A})-\min_{\pi\in\Pi} \sum_{t=1}^T c_t(\y_t^{\pi}, \uv_t^{\pi}).
\end{align*}

Here, $(\y_t^{\A}, \uv_t^{\A})$ is the observation-control pair reached by learner $\A$, and $(\y_t^{\pi}, \uv_t^{\pi})$ is the would-be observation-control pair if the policy $\pi$ was carried from the beginning of the time. It is evident from the definition of regret that the strength of regret as a performance metric strongly depends on the richness of the policy class $\Pi$. The standard benchmark policy class used in literature ([Simchowitz et al., 2020, Simchowitz, 2020, Sun et al., 2023]) is the disturbance response controller (DRC) policy class, formally given by the following definition:

(1) A disturbance response controller (DRC) is a policy $\pi_M$ of length $m$ parametrized by a sequence of $m$ matrices $M=(M^{[j]})_{j=0}^{m-1}$ of dimension $d_{\uv}\times d_{\y}$ such that the control at $t$ is given by $\uv_t^{\pi_M}=K\y_t+\sum_{j=0}^{m-1}M^{[j]}\ynat_{t-j}$, where $\ynat_t$ is the would-be observation had the linear policy $K$ been carried out from the beginning of the time.

(2) A DRC policy class $\M(m,R_{\M})$ parametrized by $(m, R_{\M})$ is the set of all disturbance response controllers of length $m$ that obey the norm bound:

\begin{align*}
\|M\|_{\ell_1,\mathrm{op}}=\sum_{j=0}^{m-1}\|M^{[j]}\|_{\mathrm{op}}\le R_{\M}.
\end{align*}

§ BANDIT NEWTON STEP FOR $\KAPPA$-CONVEX LOSSES

In this section we describe our bandit Newton algorithm (see Algorithm <ref>). At a high level, our algorithm tries to estimate the missing information (i.e., gradient and Hessian) about the unknown loss function and then takes a Newton step to compute the next action.  To estimate the gradient and Hessian at time step $t$, we employ the following randomized sampling scheme. We first sample a point uniformly from an ellipsoid centered at the current iterate $x_t$. The covariance matrix of this ellipsoid is constructed using prior Hessian estimates of the loss functions $\{f_s\}_{s=1}^{t-1}$. We then obtain one-point feedback from the adversary regarding the loss value at the sampled point.  This feedback enables gradient and Hessian estimation (see lines 3-5 of Algorithm <ref>).

Bandit Newton Step

Input: convex set $\K$, step size $\eta$, condition number $\kappa'$

[1]
Initialize: $x_1 \in\K$, $\tilde{A}_0 = I  $
$t = 1, \ldots, T$
Draw $v_{t,1}, v_{t,2}$ uniformly from $\sphere = \{x\in\real^d|\|x\|_2 = 1\}$, and let $y_t=x_t+\frac{1}{2} \tilde{A}_{t-1}^{-\frac{1}{2}}(v_{t,1}+v_{t,2})$.
Play $y_t$, observe $f_t(y_t)$.
Create gradient and Hessian estimates $\tilde{\nabla}_t,\tilde{H}_t$:

\begin{align*}
\tilde{\nabla}_{t}=2df_t(y_t) \tilde{A}_{t-1}^{\frac{1}{2}}v_{t,1}, \ \ \ \tilde{H}_{t}=2d^2 f_t(y_t)\tilde{A}_{t-1}^{\frac{1}{2}}(v_{t,1}v_{t,2}^{\top}+v_{t,2}v_{t,1}^{\top})\tilde{A}_{t-1}^{\frac{1}{2}}.
\end{align*}

Update $\tilde{A}_{t} = \tilde{A}_{t-1} + \frac{\eta}{\kappa'} \tilde{H}_t $, and compute $x_{t+1}$

\begin{align*}
&x_{t+1} = \prod_{\K}^{\tilde{A}_t} \left[ x_t - \eta \tilde{A}_t^{-1}  \tilde{\nabla}_t  \right],
\end{align*}

where $\prod_{\K}^{\tilde{A}_t}$ is the projection onto  $\K$ w.r.t $\tilde{A}_t$ norm.

Let $B^* \coloneqq B+\sqrt{2}(L+\sqrt{2}C)$. Suppose the algorithm is run with $\kappa'\geq \kappa$, and $\eta\le \kappa'(24 d^{3/2}B^*\kappa\sqrt{T\log(dT^2)})^{-1}$.  Then the following holds for any $x\in\K$:

$$   \E\left[\sum_{t=1}^T f_t(y_t)  -  f_t(x)\right] \le \frac{\mathrm{diam}(\K)^2  }{2\eta} + 3\eta d^2 (B^*)^2 T + \frac{ 2d\kappa\kappa'\log(1+ \eta CT/\kappa')} {\eta }.$$

In particular, by setting $\kappa'=\kappa$, $\eta=O( d^{-3/2} T^{-1/2})$, we have

\begin{align*}
\E[\regret_T]\le \tilde{O}(d^{2.5}\kappa^2 B^* \sqrt{T}).
\end{align*}

(Sketch) One of the key steps in the proof is to show that $\tilde{A}_{t-1}$ concentrates well around the true cumulative Hessian w.h.p (Lemma <ref>). This result implies that the iterates generated by the algorithm are well defined. Another implication of this result is that the action $y_t$ chosen by the learner is at most distance $2$ (measured in $\ell_2$ norm) away from $\K$ w.h.p. Our regret analysis relies on the following two  functions: $\smoothfBS{t}(x) \coloneqq \E_{u\sim \ball, v \sim \sphere}[f_t(x + \frac{1}{2} \tilde{A}_{t-1}^{-1/2}(u+v))|\FM_{t-1}]$, $\smoothfSS{t}(x) \coloneqq \E_{u, v \sim \sphere}[f_t(x + \frac{1}{2} \tilde{A}_{t-1}^{-1/2}(u+v))|\FM_{t-1}]$, where $\sphere = \{x\in\real^d|\|x\|_2 = 1\}$ and $\ball = \{x\in\real^d|\|x\|_2 \leq 1\}$. These two functions are different smoothed variants of $f_t$. A simple application of Stokes' theorem [Flaxman et al., 2004] shows that $\EBB[\tilde{\nabla}_t|\FM_{t-1}] = \nabla \smoothfBS{t}(x_t),$ and $\EBB[f_t(y_t)|\FM_{t-1}] = \smoothfSS{t}(x_t).$

In the rest of the proof we perform the following regret decomposition and bound each of the terms

\begin{align*}
\sum_{s=1}^{T}\E[f_s(y_s) -  f_s(x)] & = \sum_{s=1}^{T}\E[\smoothfBS{s}(x_s) -  \smoothfBS{s}(x)]  +  \E[\smoothfBS{s}(x) -  f_s(x)]  +  \E[\smoothfSS{s}(x_s) - \smoothfBS{s}(x_s)].
\end{align*}

The second and third terms capture the penalty we pay for exploration. To bound the first term, we view our algorithm as performing stochastic Newton method on the smoothed losses $\smoothfBS{t}$ (Lemma <ref>).

Running time. Most steps of the BNS algorithm can be implemented with only matrix-vector products, that  run in time $O(d^2)$ for dense matrices. In addition, its SVD can be maintained in $O(d^2)$ time using the techniques of [Arbenz and Golub, 1988, Gu and Eisenstat, 1994], since we have only rank-2 updates each iteration. This allows us to compute both the inverse and inverse square-root in linear time.

Comparison with relevant prior work.
We take a moment to compare Algorithm <ref> with that in Suggala et al., 2021, Lattimore and György, 2023. While these works have also developed bandit Newton methods, our work differs from theirs in several key aspects: (a) unlike the method of Suggala et al., 2021, which is restricted to quadratic losses, our algorithm is applicable to a broader class of loss functions. Furthermore, our approach is simple and avoids focus regions and restart conditions of Suggala et al., 2021. Finally, the regret of our algorithm has a better dependence in $d$. (b) In contrast to Lattimore and György, 2023, which focuses on stochastic losses in unconstrained domains, our algorithm is designed for the more general adversarial bandit setting in constrained domains.

§ BQO-AM WITH ACCESS TO PARTIAL HESSIAN INFORMATION

This section explores the challenge of optimizing bandit quadratic operations with memory (BQO-M), inspired by the growing interest in online convex optimization with memory (OCO-M) for its applications in nonstochastic control. Recently, [Sun et al., 2023] studied bandit control of LQR and LQG with strongly convex adversarial cost functions and semi-adversarial noises and obtained the optimal $\tilde{O}(\sqrt{T})$ regret. This motivates the inquiry of whether the same optimal regret can be established for a fully adversarial noise model.

The transition from semi-adversarial to fully adversarial models is significant, especially since strong convexity, which generally improves regret bounds in online learning, does not guarantee the same for loss functions in nonstochastic control problems faced with adversarial disturbances. Since BCO with memory is hard for general convex loss functions even if the loss functions are also quadratic (see Section <ref>), we must leverage additional structure of the control problem to obtain a better rate. [Simchowitz, 2020] established that the reduction from nonstochastic LQR/LQG problems falls within a subclass of the OCO-M framework, where the the dependence on previous decisions assumes an affine structure. This discovery enabled the derivation of the first optimal logarithmic regret bounds for LQR/LQG in the presence full adversarial disturbances. The challenge remains in extending the optimal regret bound to the bandit settings. With only scalar feedback, the learner must balance the bias and variance of the gradient estimator variance to obtain optimal regret. Without strong convexity and additional structural assumptions, this balance becomes harder to achieve. The current best regret rate in fully adversarial settings is $\tilde{O}(T^{2/3})$, as shown by [Cassel and Koren, 2020].

§.§ BQO-AM preliminaries

In the BQO-AM setting, the learner is asked to play a decision $y_t\in\mathbb{R}^d$ at time $t$. After the decision is made, an adversary reveals a quadratic cost function with memory length $m$, $f_t:(\mathbb{R}^{d})^m\rightarrow\mathbb{R}$, that is evaluated the learner's $m$ most recent decisions. $f_t$ admits the following structure:

\begin{align}
\label{eq:bqo-am-function}
\end{align}

where $G=(G^{[i]})_{i=0}^{m-1}$ is a sequence of matrices of dimension $n\times p$, $Y_{t-m+1:t}$ are $m$ matrices of dimension $p\times d$, and $B_t$ is a vector of dimension $n$. $q_t:\mathbb{R}^n\rightarrow \mathbb{R}$ is a quadratic function with Hessian $Q_t$. We assume that $\alpha I\preceq Q_t \preceq \beta I$, for some $0<\alpha\le\beta$. We note that the strong convexity assumption here does not translate to the strong convexity of $f_t$ without further assumptions on $Y_{t-m+1:t}$. We assume that the learner has access to the following quantities:

\begin{align*}
H_t =G_t^{\top}G_t \in \mathbb{R}^{d\times d}, \ \ \ G_t=\sum_{i=0}^{m-1}G^{[i]}Y_{t-i}\in \mathbb{R}^{n\times d}, \ \ \ \forall t\in[T].
\end{align*}

Let $\bar{f}_t$ denote the induced unary form of $f_t$: $\bar{f}_{t}(x)=f_t(x,\dots,x)$.
The Hessian $\nabla^2\bar{f}_{t}$ satisfy the following property: $\alpha H_t\preceq \nabla^2\bar{f}_t\preceq \beta H_t$ since $\nabla^2\bar{f}_t=G_t^{\top} Q_tG_t\in[\alpha H_t, \beta H_t]$.
We make the following regularity assumptions.
[Diameter and gradient bound]

$\K\subset\mathbb{R}^d$ has Euclidean diameter bound $D$, i.e.
$$\sup_{x,y\in\K} \|x-y\|_2 \le D.$$

The range of $f_t$ is bounded by $B$, and gradient norm is bounded $L$ over $\K^m$, $\forall t$, i.e.

\begin{align*}
\max_{t\in[T]}\sup_{z\in\K^m} |f_t(z)|\le B, \ \ \ \max_{t\in[T]}\sup_{z\in\K^m}
\|\nabla f_t(z)\|_2\le L.
\end{align*}

In existing literature on BCO-M, the algorithm holds regret guarantee against $m$-step delayed adversaries ([Gradu et al., 2020, Sun et al., 2023]). Here, we also allow the same adaptivity of the adversary:
[Adaptivity of the adversary]

The adversary is allowed to be $(t-m)$-steps adaptive. In particular, if we denote as $\F_t$ the filtration generated by the algorithm's randomness up to time $t$, then the loss function $f_t$ supplied by the adversary at time $t$ is $\F_{t-m}$-measurable.

[Exponential decay and positive convolution invertibility-modulus]

$G, Y_t$ satisfy that for $m=\poly(\log T)$,

\begin{align*}
&\kappa(G)=\min\left\{1, \inf_{\sum_{n\ge 0}\|u_n\|_2^2=1}\left\{\sum_{n=0}^{\infty}\left\|\sum_{i=0}^nG^{[i]}u_{n-i}\right\|_2^2\right\}\right\}=\Omega(1),\\
&\|G\|_{\ell_1,\mathrm{op}}=\sum_{i=0}^{m-1}\|G^{[i]}\|_{\mathrm{op}}\le R_G=O(1), \ \ \ \sum_{i=m}^{\infty}\|G^{[i]}\|_{\mathrm{op}}\le \frac{R_G}{T},\\
&\max_{0\le i\le m-1} \|(G^{[i]})^{\top}G^{[i]}\|_2\le \tilde{R}_G=O(1), \ \ \ \max_{t\in[T]}\|Y_t\|_\mathrm{op}\le R_Y=O(1).
\end{align*}

It can be shown that for nonstochastic LQR/LQG problems, Assumption <ref> is satisfied. The reduction is established in Section <ref>.

§.§ BQO-AM Algorithm and Guarantees

We introduce the following BQO-AM algorithm. The update rule resembles that of online newton step, except that the learner uses $H_t$ to update the preconditioner matrix in place of the Hessian estimator as in Algorithm <ref>.

Bandit Quadratic Optimization with Affine Memory ()

Input: convex set $\K\subset \mathbb{R}^d$, step size $\eta>0$, memory parameter $m$, time horizon $T$.

[1]
Initialize: $x_{1}=\dots=x_{m}\in\K$, $\tilde{g}_{0:m-1} = \mathbf{0}_{d}$, $ \hat{A}_{0:m-1} = mI$.
Sample $u_t\sim S^{d-1}$ i.i.d. uniformly at random for $t=1,\dots,m$.
Set $y_t = x_t + \hat{A}_{t-1}^{-\frac{1}{2}}u_t$, $t=1,\dots,m$.
$t = m, \ldots, T$
Play $y_t$, observe $f_t(y_{t-m+1:t})$, receive $H_t$.
Update $\hat{A}_t=\hat{A}_{t-1}+\frac{\eta \alpha}{2}H_t$.
Create gradient estimate:

\begin{align*}
\tilde{g}_{t}=df_t(y_{t-m+1:t}) \sum_{j=0}^{m-1}\hat{A}_{t-1-j}^{\frac{1}{2}}u_{t-j}\in\mathbb{R}^{d}.
\end{align*}

$ x_{t+1} = \prod_{\K}^{\hat{A}_{t-m+1}} \left[ x_{t} - \eta \hat{A}_{t-m+1}^{-1}  \tilde{g}_{t-m+1}  \right]$.
Sample $u_{t+1}\sim S^{d-1}$ uniformly at random, independent of previous steps.
Set $y_{t+1}=x_{t+1}+\hat{A}_{t-m+1}^{-\frac{1}{2}}u_{t+1}$.

Suppose $f_t$'s and the adversary model satisfy the assumptions in Section <ref>, and $m=\poly(\log T)$.
By setting $\eta=\tilde{\Theta}\left(\frac{1}{\alpha\sqrt{T}}\right)$, Algorithm <ref> satisfies the following regret guarantee against any $x\in\K$:

\begin{align*}
\E[\mregret_T(x)]\le \tilde{O}(\sqrt{T}).
\end{align*}

§.§ Reduction from the Bandit LQR/LQG problem

The control problem described in Section <ref> can be formulated as a BQO-AM problem defined in Section <ref>. In particular, $\exists f_t$ of the form Eq. (<ref>) satisfying Assumption (<ref>)-(<ref>) such that the cost function $c_t$ defined in Section <ref> can be expressed by $f_t$. The reduction is formally proved in Section <ref> and <ref>. This reduction makes it possible to directly adapt Algorithm <ref> to the control setting. The control algorithm, which we refer to as Newton Bandit Perturbation Controller (), is specified in Section <ref>. The regret guarantee of  is stated in Theorem <ref>. An extension of the result to unknown systems is included in Appendix <ref>.

Suppose $c_t$'s and the adversary model satisfy the assumptions in Section <ref>, and $m=\poly(\log T)$.
By setting $\eta=\tilde{\Theta}\left(\frac{1}{\alpha\sqrt{T}}\right)$,  (Algorithm <ref>) satisfies the following regret guarantee:

\begin{align*}
\E[\cregret_T(\texttt{NBPC})]=\E\left[\sum_{t=1}^T c_t(\y_t,\uv_t)-\min_{M\in\M(m,R_{\M})}\sum_{t=1}^T c_t(\y_t^M,\uv_t^M)\right]\le \tilde{O}(\sqrt{T}).
\end{align*}

§ LOWER BOUND FOR BCO-M

Now we turn our attention to the general problem of BCO-M.
We are interested in a lower bound under Assumption <ref>.

We show a regret lower bound of $\tilde{\Omega}(T^{2/3})$ for this setting even for quadratic and smooth loss functions and $m=2$. This result holds even if we allow some degree of improper learning.

There exists a sequence of loss functions such that the regret incurred by any (possibly randomized) online bandit quadratic optimization with memory length $m\ge 2$ algorithm $\A$ is at least $\tilde{\Omega}(T^{2/3})$.

A matching upper bound for quadratic and smooth functions in the presence of $\F_{t-m}$-adaptive adversary can also be established. We believe that the algorithm in [Cassel and Koren, 2020] can also be generalized to scenarios where the adversary is allowed to be $\F_{t-m}$-adaptive. However, since this was not spelled out explicitly, we give an alternative first-order proper learning algorithm for completeness in Section <ref>.

§ CONCLUSIONS, DISCUSSIONS, AND FUTURE WORK

In this paper, we considered a bandit version of the Online Newton Step algorithm that attains near-optimal regret bounds for a large class of convex loss functions we call $\kappa$-convex with a low dimension dependence.
In addition to the application to bandit convex optimization, we showed how our methods close an open problem in online control and separated the difficulty of bandit LQR/LQG and the general BCO-M problem.
Many interesting open questions remain:

* Proper BCO for $\kappa$-convex losses.
It is interesting to see whether there exists efficient proper learning algorithm that achieves a $O(\sqrt{T})$ regret with reasonable dependence on the dimension for the class of $\kappa$-convex problems.

* Extension to nonstochastic control with general cost functions. It is worth exploring if tighter bounds are achievable for bandit linear control with general convex loss functions with adversarial perturbations.

* Lower bound for oblivious adversary. If the adversary is oblivious in BCO-M problems, we are interested in whether $\Omega(T^{2/3})$ regret lower bound can be achieved.

[Abeille and Lazaric, 2017]
Marc Abeille and Alessandro Lazaric.
Linear thompson sampling revisited.
In Artificial Intelligence and Statistics, pages 176–184.
PMLR, 2017.

[Abernethy et al., 2009]
Jacob D Abernethy, Elad Hazan, and Alexander Rakhlin.
Competing in the dark: An efficient algorithm for bandit linear

[Agarwal et al., 2019]
Naman Agarwal, Brian Bullins, Elad Hazan, Sham Kakade, and Karan Singh.
Online control with adversarial disturbances.
In International Conference on Machine Learning, pages
111–119. PMLR, 2019.

[Anava et al., 2015]
Oren Anava, Elad Hazan, and Shie Mannor.
Online learning for adversaries with memory: price of past mistakes.
Advances in Neural Information Processing Systems, 28, 2015.

[Arbenz and Golub, 1988]
Peter Arbenz and Gene H. Golub.
On the spectral decomposition of hermitian matrices modified by low
rank perturbations with applications.
SIAM Journal on Matrix Analysis and Applications, 90
(1):0 40–58, 1988.

[Bubeck et al., 2017]
Sébastien Bubeck, Yin Tat Lee, and Ronen Eldan.
Kernel-based methods for bandit convex optimization.
In Proceedings of the 49th Annual ACM SIGACT Symposium on
Theory of Computing, pages 72–85, 2017.

[Bubeck et al., 2021]
Sébastien Bubeck, Ronen Eldan, and Yin Tat Lee.
Kernel-based methods for bandit convex optimization.
Journal of the ACM (JACM), 680 (4):0 1–35,

[Bullins et al., 2016]
Brian Bullins, Elad Hazan, and Tomer Koren.
The limits of learning with missing data.
Advances in Neural Information Processing Systems, 29, 2016.

[Cassel and Koren, 2020]
Asaf Cassel and Tomer Koren.
Bandit linear control.
Advances in Neural Information Processing Systems,
33:0 8872–8882, 2020.

[Cesa-Bianchi et al., 2011]
Nicolo Cesa-Bianchi, Shai Shalev-Shwartz, and Ohad Shamir.
Efficient learning with partially observed attributes.
Journal of Machine Learning Research, 120 (10), 2011.

[Cesa-Bianchi et al., 2013]
Nicolo Cesa-Bianchi, Ofer Dekel, and Ohad Shamir.
Online learning with switching costs and other adaptive adversaries.
Advances in Neural Information Processing Systems, 26, 2013.

[Chen and Hazan, 2021]
Xinyi Chen and Elad Hazan.
Black-box control for linear dynamical systems.
In Conference on Learning Theory, pages 1114–1143. PMLR,

[Dekel et al., 2014]
Ofer Dekel, Jian Ding, Tomer Koren, and Yuval Peres.
Bandits with switching costs: T 2/3 regret.
In Proceedings of the forty-sixth annual ACM symposium on
Theory of computing, pages 459–467, 2014.

[Dong et al., 2019]
Shi Dong, Tengyu Ma, and Benjamin Van Roy.
On the performance of thompson sampling on logistic bandits.
In Conference on Learning Theory, pages 1158–1160. PMLR,

[Faury et al., 2022]
Louis Faury, Marc Abeille, Kwang-Sung Jun, and Clément Calauzènes.
Jointly efficient and optimal algorithms for logistic bandits.
In International Conference on Artificial Intelligence and
Statistics, pages 546–580. PMLR, 2022.

[Flaxman et al., 2004]
Abraham D Flaxman, Adam Tauman Kalai, and H Brendan McMahan.
Online convex optimization in the bandit setting: gradient descent
without a gradient.
arXiv preprint cs/0408007, 2004.

[Foster et al., 2018]
Dylan J Foster, Satyen Kale, Haipeng Luo, Mehryar Mohri, and Karthik Sridharan.
Logistic regression: The importance of being improper.
In Conference On Learning Theory, pages 167–208. PMLR, 2018.

[Gradu et al., 2020]
Paula Gradu, John Hallman, and Elad Hazan.
Non-stochastic control with bandit feedback.
Advances in Neural Information Processing Systems,
33:0 10764–10774, 2020.

[Gu and Eisenstat, 1994]
Ming Gu and Stanley C Eisenstat.
A stable and efficient algorithm for the rank-one modification of the
symmetric eigenproblem.
SIAM journal on Matrix Analysis and Applications, 150
(4):0 1266–1276, 1994.

[Hazan, 2022]
Elad Hazan.
Introduction to online convex optimization.
MIT Press, 2022.

[Hazan and Kale, 2011]
Elad Hazan and Satyen Kale.
Newtron: an efficient bandit algorithm for online multiclass
Advances in neural information processing systems, 24, 2011.

[Hazan and Koren, 2012]
Elad Hazan and Tomer Koren.
Linear regression with limited observation.
arXiv preprint arXiv:1206.4678, 2012.

[Hazan and Levy, 2014]
Elad Hazan and Kfir Levy.
Bandit convex optimization: Towards tight bounds.
Advances in Neural Information Processing Systems, 27, 2014.

[Hazan and Singh, 2022]
Elad Hazan and Karan Singh.
Introduction to online nonstochastic control.
arXiv preprint arXiv:2211.09619, 2022.

[Hazan et al., 2007]
Elad Hazan, Amit Agarwal, and Satyen Kale.
Logarithmic regret algorithms for online convex optimization.
Machine Learning, 69:0 169–192, 2007.

[Hazan et al., 2014]
Elad Hazan, Tomer Koren, and Kfir Y Levy.
Logistic regression: Tight bounds for stochastic and online
In Conference on Learning Theory, pages 197–209. PMLR, 2014.

[Koren et al., 2017]
Tomer Koren, Roi Livni, and Yishay Mansour.
Multi-armed bandits with metric movement costs.
Advances in Neural Information Processing Systems, 30, 2017.

[Lattimore, 2020]
Tor Lattimore.
Improved regret for zeroth-order adversarial bandit convex
Mathematical Statistics and Learning, 20 (3):0
311–334, 2020.

[Lattimore and Gyorgy, 2021]
Tor Lattimore and Andras Gyorgy.
Improved regret for zeroth-order stochastic convex bandits.
In Conference on Learning Theory, pages 2938–2964. PMLR,

[Lattimore and György, 2023]
Tor Lattimore and András György.
A second-order method for stochastic bandit convex optimisation.
arXiv preprint arXiv:2302.05371, 2023.

[Lattimore and Szepesvári, 2020]
Tor Lattimore and Csaba Szepesvári.
Bandit algorithms.
Cambridge University Press, 2020.

[McMahan and Streeter, 2012]
H Brendan McMahan and Matthew Streeter.
Open problem: Better bounds for online logistic regression.
In Conference on Learning Theory, pages 44–1. JMLR Workshop
and Conference Proceedings, 2012.

[Shamir, 2013]
Ohad Shamir.
On the complexity of bandit and derivative-free stochastic convex
In Conference on Learning Theory, pages 3–24. PMLR, 2013.

[Simchowitz, 2020]
Max Simchowitz.
Making non-stochastic control (almost) as easy as stochastic.
Advances in Neural Information Processing Systems,
33:0 18318–18329, 2020.

[Simchowitz et al., 2020]
Max Simchowitz, Karan Singh, and Elad Hazan.
Improper learning for non-stochastic control.
In Conference on Learning Theory, pages 3320–3436. PMLR,

[Suggala et al., 2021]
Arun Sai Suggala, Pradeep Ravikumar, and Praneeth Netrapalli.
Efficient bandit convex optimization: Beyond linear losses.
In Conference on Learning Theory, pages 4008–4067. PMLR,

[Sun et al., 2023]
Y Jennifer Sun, Stephen Newman, and Elad Hazan.
Optimal rates for bandit nonstochastic control.
arXiv preprint arXiv:2305.15352, 2023.

[Tropp, 2011]
Joel Tropp.
Freedman's inequality for matrix martingales.

§ APPLICATIONS OF BANDIT NEWTON STEP

In this section, we illustrate the applicability of our bandit Newton method (Algorithm <ref>) to a few problems where it achieves optimal regret guarantees. First, we acknowledge that since the algorithm in Bubeck et al., 2021 works for a richer class of loss functions than ours, applying their algorithm will also give the optimal regret bounds in terms of $T$ in these applications. However, the high polynomial dependence on the dimension ($d^{9.5}$) and the $\mathrm{poly}(d,T)$ amortized running time make the algorithm by [Bubeck et al., 2021] impractical in many real-world applications. Therefore, for simplicity, we are going to exclude the comparison with [Bubeck et al., 2021] in this section.

§.§ Online Logistic Regression

Logistic regression is a widely utilized and effective technique for performing classification tasks. For simplicity, we consider binary classification. In this framework, the goal is to predict the probability that a given input point belongs to one of two possible classes. These classes are typically represented by the label set $\Y=\{-1,1\}$. The foundational assumption of logistic regression is that the log-odds, or the logarithm of the odds ratio between the two classes, can be linearly modeled by the input features. Mathematically, this relationship is expressed as:

\begin{align*}
\log\left(\frac{\mathbb{P}(Y=1\mid X=x)}{1-\mathbb{P}(Y=1\mid X=x)}\right)=w^{\top}x+b,
\end{align*}

where $x$ denotes the feature vector, $w$ represents the weight vector, and $b$ is the bias term. This formulation provides a linear decision boundary in the feature space.

In the online setting of logistic regression, the learning process is sequential and adaptive. At each time step $t$, an adversary presents a new instance, consisting of a feature vector and a label $(x_t,y_t)\in\mathbb{R}^d\times \{-1,1\}$. Subsequently, the learning algorithm selects a linear predictor $w_t$ from a set $\mathcal{W}=\{w\in\mathbb{R}^d:\|w\|_2\le D\}$, where $\|w\|_2\le D$ ensures that the chosen predictor does not have excessively large weights, thereby controlling the model's complexity.
The performance of the predictor $w_t$ is then evaluated based on the incurred loss, which, for logistic regression, is defined as:

\begin{align*}
f_t(w_t)=f(w_t;x_t, y_t)=\log(1+\exp(-y_t\cdot x_t^{\top}w_t)).
\end{align*}

In the bandit framework, where the sequence of labeled data may be confidential and not directly observable by the learner, the learner is only exposed to a scalar classification cost, denoted as $f_t(w_t)$.
It is often assumed for simplicity that $\|x_t\|_2\le 1$, $\forall t$, in which case the Hessian of $f_t$ satisfies

\begin{align*}
\frac{e^{-D}}{(1+e^{-D})^2}x_tx_t^{\top}\preceq \nabla^2 f_t(w_t) = \frac{\exp(-y_t\cdot x_t^\top w_t)} {(1 + \exp(-y_t\cdot x_t^\top w_t))^2} \cdot x_tx_{t}^{\top}\preceq \frac{1}{2}x_tx_t^{\top}.
\end{align*}

This shows that $f_t$ is $\kappa$-convex with $\kappa=\exp(D)$, making it suitable to apply Algorithm <ref>.

Suppose a learner is playing over a decision set $\mathcal{W}$ with diameter bound $D$ against an oblivious adversary picking a labeled vector $(x_t,y_t)\in\mathbb{R}^d\times \{-1,1\}$ with $\|x_t\|_2\le 1$, then Algorithm <ref> guarantees

\begin{align*}
\E[\regret_T]=\E\left[\sum_{t=1}^T f(w_t; x_t, y_t) - \min_{w\in\mathcal{W}}\sum_{t=1}^T f(w; x_t,y_t)\right]\le O(d^{2.5}e^{2D}\sqrt{T}).
\end{align*}

Let's take a moment to compare the result of Corollary <ref> with existing results. To the best of our knowledge, this is the first bandit logistic regression algorithm that works against adversarially chosen labeled vectors that achieves an optimal regret bound in $T$ and $d^{5/2}$ dependence on $d$.
Table <ref> summarized some of the state-of-art results in the field. First, let's focus on the logistic bandits setting. [Hazan and Kale, 2011] and [Foster et al., 2018] both studied the problem which they refer to as bandit multi-class prediction, which we refer to as the semi-bandit feedback model in Table <ref>. In this setting, although the learner accesses loss through bandit feedback, the vector $x_t$ is revealed to the learner. The more general case where both the vector and the label are given to the learner through bandit feedback was studied only under stochastic assumption on the input vector, in which case $\tilde{O}(e^D\sqrt{T})$ and $\tilde{O}(\sqrt{T})$ bounds were achieved by [Abeille and Lazaric, 2017] and [Dong et al., 2019] for frequentist and Bayesian regret bounds, respectively.

One question remaining is regarding the exponential dependence on $D$ in the bound of Corollary <ref>. To shed some light on this question, we consider the full information setting. [Hazan et al., 2007] showed that running online newton step gives the optimal dependence ($\log T$) in $T$ but suffers an exponential factor in terms of the diameter $D$, leading to the open problem of whether a $\tilde{O}(\mathrm{poly}(D))$ regret bound is attainable in [McMahan and Streeter, 2012]. Later, [Hazan and Levy, 2014] showed a negative result that for $d\ge 2$, the regret for this problem is at least $\tilde{\Omega}(e^D\vee \sqrt{DT})$ if the algorithm is proper, i.e. $w_t\in\mathcal{W}$. [Foster et al., 2018] showed that when allowing improper learning, $\tilde{O}(1)$-regret bound is attainable. It will be an interesting open problem to investigate whether the exponential dependence on $D$ can be dropped in logistic bandits.

Paper     Feedback     Advers.     Proper     Regret     Comp.     Note

[Hazan et al., 2007]      full        $\checkmark$     $\checkmark$      $\tilde{O}(e^D)$     $O(d^2)$

[Hazan et al., 2014]      full        $\times$     $\checkmark$      $\tilde{\Omega}(e^{D}\vee \sqrt{DT})$     –

[Foster et al., 2018]      full       $\checkmark$     $\times$      $\tilde{O}(1)$      $\mathrm{poly}(d,T)$

[Hazan and Kale, 2011]      semi-bandit      $\checkmark$     $\checkmark$     $\tilde{O}(e^D \wedge DT^{2/3})$      $O(d^2)$

[Foster et al., 2018]      semi-bandit      $\checkmark$     $\times$     $\tilde{O}(e^D \wedge \sqrt{T})$     $\mathrm{poly}(d,T)$

[Dong et al., 2019]      bandit      $\times$     $\checkmark$     $\tilde{O}(\sqrt{T})$      $\mathrm{poly}(d)$     Bayesian

[Faury et al., 2022]      bandit      $\times$     $\checkmark$     $\tilde{O}(e^D \vee \sqrt{T})$      $O(d^2)$     frequentist

Corollary <ref>      bandit     $\checkmark$     $\times$     $O(e^{2D}\sqrt{T})$    $O(d^{2})$

Comparison with relevant prior works for online logistic regression. $\tilde{O}, \tilde{\Omega}$ in the regret column hide all parameters other than $D,T$ and logarithmic factors in $D,T$.

§.§ Online Linear Regression with Limited Observations

Consider the standard online learning setting for linear regression problems. At each time $t$, the learner is supplied with a vector $x_t\in\mathcal{X}\subset\mathbb{R}^d$ and is asked to output a weight vector $w_t\in\mathcal{W}\subset\mathbb{R}^d$ such that the learner's label prediction for $x_t$ is $\hat{y}_t=w_t^{\top}x_t\in \mathbb{R}$. After the learner outputs $w_t$, the adversary reveals the true label $y_t$, to which the learner suffers loss $f(w_t;x_t)=(\hat{y}_t-y_t)^2$.

Previous works such as [Cesa-Bianchi et al., 2011, Hazan and Koren, 2012, Bullins et al., 2016] have considered this framework in the setting of limited observations. In the limited observation setting, the learner observes only a subset of the attributes in $x_t$. We consider a more generalized version of the problem, where the learner does not necessarily observe $(x_t,y_t)$ at all but simply a scalar loss of $f(w_t;x_t)\in\mathbb{R}_+$. Note that the loss is $\kappa$-convex with $\kappa=1$.

Suppose a learner is playing over a decision set $\mathcal{W}$ with diameter bound $D_{\mathcal{W}}$ against an oblivious adversary picking a labeled vector $(x_t,y_t)$, then Algorithm <ref> guarantees

\begin{align*}
\E[\regret_T]=\E\left[\sum_{t=1}^T f(w_t;x_t)-\min_{w\in\mathcal{W}}\sum_{t=1}^T f(w;x_t)\right]\le O(d^{2.5}\sqrt{T}).
\end{align*}

§.§ Bandit PCA and Eigenvector Learning

The problem of online spectral learning was initially considered in the context of variance minimization <cit.>.
In this problem, the learner predicts a vector $x_t$, and obtains a loss according to a quadratic function, which is not necessarily convex, $x_t^\top M x_t$.

§.§ Bandit Learning of Quantum States

literature: shaddow tomography of Scott, previous online learning of quantum states. The bandit version of this problem is called "Quantum process learning", see paper by Huang and Preskill (<cit.>)

In the online version of quantum tomography, also called online learning of quantum states, a learner iteratively predicts a quantum state over $d$ cubits $\omega_t \in \mathcal{C}^{2^d \times 2^d} \ , \ \omega_t = \omega_t^\dagger \  , \ \omega_t \succeq 0 \ , \  \trace(\omega_t) = 1$. The learner then suffers a loss according to an adversarially chosen measurement matrix $E_t \in \mathcal{C}^{2^d \times 2^d}$, which is a Hemitian matrix with eigenvalues in $[0,1]$. The loss is given by

$$ \ell_t(\omega_t) = (w_t \bullet E_t - b_t)^2 , $$

where $b_t$ usually represents the outcome of a measurement with an underlying quantum state.

The loss functions of online quantum state learning are $\kappa$-convex, since the Hessian is given by the matrix $E_t E_t^\top$. The bandit version of this problem can thus be solved with optimal regret, and via our efficient Newton-based algorithm.

§.§ Applications of BCO algorithm

§.§ Generalized Linear Bandits

Stochastic Setting. <cit.>

Adversarial Setting. Linear bandits <cit.> this seems to be a paper about BLO?

§ ONLINE NEWTON STEP IN FULL INFORMATION SETTING

Online Newton Step (ONS)

Input: convex set $\K$, step size $\eta$, Hessian multiplier $\kappa'$

[1]
Initialize: $x_1 \in\K$, $A_0 = I  $
$t = 1, \ldots, T$
Play $x_t$, observe $f_t$.

Update $A_{t} = A_{t-1} + \frac{\eta}{\kappa'} \nabla^2f_t(x_t) $, and compute $x_{t+1}$

\begin{align*}
&x_{t+1} = \prod_{\K}^{A_t} \left[ x_t - \eta A_t^{-1}  \nabla f_t(x_t)  \right]
\end{align*}

For the Online Newton Step Algorithm <ref> applied to a  sequence of loss functions $\{f_t\}_{t=1\dots T}$ that are twice differentiable. Moreover, suppose $\{A_t\}_{t=1\dots T}$, the cumulative Hessians, are PSD and invertible.
Then, Algorithm <ref>  guarantees the following for any $x\in \K$, and any $T\geq 1$

\[
\sum_{t=1}^T f_t(x_t) - f_t(x) \leq \frac{\text{diam}(\K)^2}{2\eta} + \sum_{t=1}^T \frac{\eta}{2} \norm{\nabla f_t(x_t)}_{A_t^{-1}}^2 - \sum_{t=1}^T\Delta_t(x).
\]

Here, $\Delta_t(x)$ is defined as

\begin{align*}
\Delta_t(x) \coloneqq f_t(x) - f_t(x_t) - \inp{\nabla f_t(x_t)}{x - x_t} - \frac{1}{2\kappa'}(x-x_t)^{\top}\nabla^2f_t(x_t)(x-x_t).
\end{align*}

For any $x\in \K$, we have that

\begin{align*}
\norm{x_{t+1} - x}_{A_t}^2 &\stackrel{(a)}{\le} \norm{x_t - \eta A_t^{-1}\nabla f_t(x_t) - x}_{A_t}^2 \\
&= \norm{x_t - x}_{A_t}^2 - 2\eta \inp{A_t^{-1}\nabla f_t(x_t)}{x_t - x}_{A_t} + \eta^2 \norm{A_t^{-1}\nabla f_t(x_t)}_{A_t}^2 \\
&= \norm{x_t - x}_{A_{t}}^2 - 2\eta  \inp{\nabla f_t(x_t)}{x - x_t} + \eta^2 \norm{\nabla f_t(x_t)}_{A_t^{-1}}^2  \\
&= \norm{x_t - x}_{A_{t-1}}^2 + 2\eta \left(\frac{1}{2\kappa'}\norm{x_t - x}_{\nabla^2f_t(x_t)}^2  + \inp{\nabla f_t(x_t)}{x - x_t}\right) + \eta^2 \norm{\nabla f_t(x_t)}_{A_t^{-1}}^2.
\end{align*}

Where $(a)$ is due to the projection property.
Now, consider the second term in the RHS above. We rewrite it as

\begin{align*}
\frac{1}{2\kappa'}\norm{x_t - x}_{\nabla^2f_t(x_t)}^2  + \inp{\nabla f_t(x_t)}{x - x_t}
&= f_t(x) - f_t(x_t) - \Delta_t(x)
\end{align*}

Substituting this in the previous display, and rearranging the terms gives us

\[
f_t(x_t) - f_t(x) \leq \frac{\norm{x_t - x}_{A_{t-1}}^2 - \norm{x_t - x}_{A_{t}}^2}{2\eta} + \frac{\eta}{2} \norm{\nabla f_t(x_t)}_{A_t^{-1}}^2 - \Delta_t(x).
\]

Summing this over $t = 1 \dots T$ gives us

\[
\sum_{t=1}^T f_t(x_t) - f_t(x) \leq \frac{\norm{x_1 - x}_2^2}{2\eta} + \sum_{t=1}^T \frac{\eta}{2} \norm{\nabla f_t(x_t)}_{A_t^{-1}}^2 - \sum_{t=1}^T\Delta_t(x).
\]

We now use the fact that $\norm{x_1 - x} \leq \text{diam}(\K)$ to obtain the desired bound

§ REGRET OF BANDIT NEWTON METHOD FOR IMPROPER LEARNING (SECTION <REF>)

We first provide a result which converts any online second order algorithm in full information setting to one that uses stochastic gradients and Hessians. In Section <ref>, we rely on this result to bound the regret of Algorithm <ref>.

Let $x$ be any fixed point in $\K$. Let $\A$ be a second order online algorithm that ensures a regret bound of the following form for any sequence of loss functions $\{f_t\}_{t=1\dots T}$ that are double differentiable

\[
\sum_{t=1}^T f_t(x_t) - f_t(x) \leq B_{\A, x}(f_1, \dots f_T).
\]

Define the points $\{x_t\}$ as: $x_1 \leftarrow \A(\emptyset),$ $x_t \leftarrow \A(\tilde{\nabla}_1, \dots \tilde{\nabla}_{t-1}, \tilde{H}_1, \dots \tilde{H}_{t-1})$, where $\tilde{\nabla}_t$ is an unbiased estimate of the gradient of $f_t$ at $x_t$ that satisfies:
$\EBB[\tilde{\nabla}_t|x_1,f_1,\dots x_t, f_t] = \nabla f_t(x_t),$
and $\tilde{H}_t$ is a stochastic estimate of $\nabla^2 f_t(x_t).$ Define the stochastic approximations of $f_t:\K\to\RBB$ as follows:

\[
h_t(x) = \inp{\tilde{\nabla}_t}{x} + \frac{1}{2}(x-x_t)^{\top}\tilde{H}_t (x-x_t)
\]

Then the following holds for any $x \in \K$

\[
\sum_{t=1}^T \EBB\left[f_t(x_t) - f_t(x)\right] \leq \EBB\left[B_{\A, x}(h_1, \dots h_T)\right] - \sum_{t=1}^T \EBB[\Delta_t(x)],
\]

where $\Delta_t(x)$ is the error in second order Taylor series expansion of $f_t$ which is defined as

\[
\Delta_t(x) \coloneqq f_t(x) - f_t(x_t) - \inp{\nabla f_t(x_t)}{x-x_t} -  \frac{1}{2}(x-x_t)^{\top}\EBB[\tilde{H}_t|x_1, f_1, \dots x_t, f_t] (x-x_t).
\]

Observe that from the definition of $h_t$, we have $\nabla h_t(x_t) = \tilde{\nabla}_t, \nabla^2 h_t(x_t) = \tilde{H}_t$. So, deterministically applying a second order algorithm $\A$ on $h_t$ is equivalent to stochastically applying $\A$ on functions $f_t$. So, we have

\begin{align}
\label{eqn:stochastic_ons_regret_intd}
\sum_{t=1}^T h_t(x_t) - h_t(x) \leq B_{\A, x}(h_1, \dots h_T).
\end{align}

Next, note that

\begin{align*}
\EBB[h_t(x_t)] \stackrel{(a)}{=}  \EBB\left[\inp{\EBB[\tilde{\nabla}_t|x_1,f_1,\dots x_t, f_t]}{x_t}\right] = \EBB\left[\inp{\nabla f_t(x_t)}{x_t}\right],
\end{align*}

where we used the fact that $\tilde{\nabla}_t$ is an unbiased estimate of the true gradient in $(a)$. A similar argument shows that

\begin{align*}
\EBB[h_t(x)] = \EBB\left[\inp{\nabla f_t(x_t)}{x}\right] + \frac{1}{2}\EBB\left[(x-x_t)^{\top}\EBB[\tilde{H}_t|x_1, f_1, \dots x_t, f_t] (x-x_t)\right].
\end{align*}

So, we have

\begin{align*}
\EBB[h_t(x_t) - h_t(x)] &= \EBB\left[\inp{\nabla f_t(x_t)}{x_t-x} \right] - \frac{1}{2}\EBB\left[(x-x_t)^{\top}\EBB[\tilde{H}_t|x_1, f_1, \dots x_t, f_t] (x-x_t)\right]\\
& = \EBB[f_t(x_t) - f_t(x) + \Delta_t(x)].
\end{align*}

The Lemma now follows by taking expectations in Equation (<ref>).

§.§ Concentration of Cumulative Hessian Estimate

Define the smoothed function $\smoothfBB{t}$ as

\[
\smoothfBB{t}(x) \coloneqq \E_{u\sim \ball, v \sim \ball}\left[f_t\left(x + \frac{1}{2} \tilde{A}_{t-1}^{-\frac{1}{2}}(u+v)\right)\Big| \FM_{t-1}\right].
\]

Let $\tilde{A}_t=\tilde{A}_{t-1}+\frac{\eta}{\kappa'}\tilde{H}_{t}$, and $A_{t}=A_{t-1}+\frac{\eta}{\kappa'}\nabla^2\smoothfBB{t}(x_t)$, where $A_0=\tilde{A}_{0}=I$. Let $B^*=B+\sqrt{2}(L+\sqrt{2}C)$. Suppose $T = \tilde{\Omega}(d)$, and $\eta\le \kappa'(24 d^{3/2}B^*\kappa\sqrt{T\log(dT^2)})^{-1}$, $\forall t$, with probability at least $1-\frac{t}{T^2}$, for every $s\le t$,

\begin{align*}
\|I-A_{s}^{-\frac{1}{2}}\tilde{A}_sA_{s}^{-\frac{1}{2}}\|_2\le \frac{1}{2}.
\end{align*}

First observe that using Stokes' theorem [Flaxman et al., 2004], we have

\[
\E[\tilde{H}_t\mid \FM_{t-1}] = \nabla^2 \smoothfBB{t}(x_t)
\]

where $\FM_t$ denotes the filtration generated by $\{v_{s,1},v_{s,2}\}_{s=1}^{t}$.

Proof by induction. Base case $t=0$ is given by construction. Suppose the inequalities hold with probability at least $1-\frac{t-1}{T^2}$ for any $0\le s\le t-1$. Recall that $f_t$ is assumed to be bounded by $B$ and $L$-Lipschitz over $\K$ and $C$-smooth. Note that $|f_t(y_t)|$ is bounded by

\begin{align*}
|f_t(y_t)|&\le |f_t(x_t)|+\left|f_t\left(x_t+\frac{1}{2}\tilde{A}_{t-1}^{-\frac{1}{2}}(v_{t,1}+v_{t,2})\right)-f_t(x_t)\right|\\
&\le B +  \left\|\nabla f_t\left(x_t+\frac{1}{2}\tilde{A}_{t-1}^{-\frac{1}{2}}(v_{t,1}+v_{t,2})\right)\right\|_2 \left\|\frac{1}{2}\tilde{A}_{t-1}^{-\frac{1}{2}}(v_{t,1}+v_{t,2})\right\|_2\\
&\le B+\left(L+C\left\|\frac{1}{2}\tilde{A}_{t-1}^{-\frac{1}{2}}(v_{t,1}+v_{t,2})\right\|_2\right)\left\|\frac{1}{2}\tilde{A}_{t-1}^{-\frac{1}{2}}(v_{t,1}+v_{t,2})\right\|_2\\
&\le B+(L+C\|\tilde{A}_{t-1}^{-\frac{1}{2}}\|_2)\|\tilde{A}_{t-1}^{-\frac{1}{2}}\|_2.
\end{align*}

By induction hypothesis, with probability at least $1-\frac{t-1}{T^2}$, $\tilde{A}_{t-1}\succeq \frac{1}{2}A_{t-1}\succeq \frac{1}{2}I$, and thus the above inequality implies $|f_t(y_t)|\le B+\sqrt{2}\left(L+\sqrt{2}C\right)=:B^*$.
Next, define $L_t$ and $U_t$ as follows

\[
L_t \coloneqq I + \frac{c\eta}{\kappa'} \sum_{s=1}^t H_s , \quad U_t \coloneqq I + \frac{C\eta}{\kappa'} \sum_{s=1}^t H_s.
\]

Observe that from our definition of $\kappa$-convex losses, $A_t$ can be lower and upper bounded as follows

\[
L_t \preceq A_t \preceq U_t.
\]

Now consider the following

\begin{align*}
\|I-A_{t}^{-\frac{1}{2}}\tilde{A}_tA_{t}^{-\frac{1}{2}}\|_2 &= \| A_{t}^{-\frac{1}{2}}(A_{t} - \tilde{A}_{t})A_{t}^{-\frac{1}{2}}\|_2\\
& \leq \|A_{t}^{-\frac{1}{2}}L_t^{1/2}\|_2^2\|L_{t}^{-\frac{1}{2}}(A_{t} - \tilde{A}_{t})L_{t}^{-\frac{1}{2}}\|_2\\
& \stackrel{(a)}{\leq} \|L_{t}^{-\frac{1}{2}}(A_{t} - \tilde{A}_{t})L_{t}^{-\frac{1}{2}}\|_2,
\end{align*}

where $(a)$ follows from the fact that $L_t \preceq A_t$. This shows that it suffices to bound $\|L_{t}^{-\frac{1}{2}}(A_{t} - \tilde{A}_{t})L_{t}^{-\frac{1}{2}}\|_2$. Next, consider the following

\begin{align*}
L_{t}^{-\frac{1}{2}}(A_{t} - \tilde{A}_{t})L_{t}^{-\frac{1}{2}}&=\frac{\eta}{\kappa'} \sum_{s=1}^t L_{t}^{-\frac{1}{2}}(\E[\tilde{H}_s\mid \FM_{s-1}]-\tilde{H}_s)L_{t}^{-\frac{1}{2}},
\end{align*}

where $Z_s=L_{t}^{-\frac{1}{2}}(\E[\tilde{H}_s\mid \FM_{s-1}]-\tilde{H}_s)L_{t}^{-\frac{1}{2}}$ forms a martingale sequence  with respect to the filtration $\FM_{s}$. We  rely on matrix Freedman inequality to bound $\|\sum_{s=1}^t Z_s\|$ [Tropp, 2011]. To do this, we derive bounds for the first and second moments of $Z_s$.

Bounding $Z_s$. We first show that $Z_s$ is a bounded random variable. To see this, note that by definition of $\tilde{H}_t$, and the fact that  $-2I\preceq v_{t,1}v_{t,2}^{\top}+v_{t,2}v_{t,1}^{\top}\preceq 2I$, we have

\begin{align*}
&-4d^2B^*\tilde{A}_{s-1}\preceq \tilde{H}_s\preceq 4d^2B^*\tilde{A}_{s-1},\\
&-4d^2B^*\tilde{A}_{s-1}\preceq \E[\tilde{H}_s\mid \FM_{s-1}]\preceq 4d^2B^*\tilde{A}_{s-1}.
\end{align*}

Thus, with probability at least $1-\frac{t-1}{T^2}$, $\forall s\le t$,

\begin{align*}
Z_s&\preceq 8d^2B^*L_{t}^{-\frac{1}{2}}\tilde{A}_{s-1}L_{t}^{-\frac{1}{2}}\\
&\preceq 8d^2B^* L_{s-1}^{-\frac{1}{2}}\tilde{A}_{s-1}L_{s-1}^{-\frac{1}{2}}\\
&\stackrel{(a)}{\preceq} 8d^2B^* \kappa A_{s-1}^{-\frac{1}{2}}\tilde{A}_{s-1}A_{s-1}^{-\frac{1}{2}}\\
&\stackrel{(b)}{\preceq} 12d^2B^*\kappa I,
\end{align*}

\begin{align*}
Z_s&\succeq -4d^2B^*L_t^{-\frac{1}{2}} \tilde{A}_{s-1} L_t^{-\frac{1}{2}}\\
&\succeq -4d^2B^* L_{s-1}^{-\frac{1}{2}}\tilde{A}_{s-1}L_{s-1}^{-\frac{1}{2}}\\
&\stackrel{(c)}{\succeq} -4d^2B^*\kappa A_{s-1}^{-\frac{1}{2}}\tilde{A}_{s-1}A_{s-1}^{-\frac{1}{2}}\\
& \stackrel{(d)}{\succeq} -6d^2B^*\kappa I,
\end{align*}

where $(a), (c)$ follow from the definition of $L_t, U_t$ and the fact that the losses are $\kappa$-convex, and $(b), (d)$ follow from the induction hypothesis that $\|I-A_{s}^{-\frac{1}{2}}\tilde{A}_sA_{s}^{-\frac{1}{2}}\|_2\le \frac{1}{2}$ and  $\tilde{A}_s$ is PSD $, \forall s\le t-1$ w.h.p.

Bounding $2^{nd}$ moments of $Z_s$. Next, we bound the second moments of $Z_s$

\begin{align*}
\EBB[Z_s^2|\FM_{s-1}] \stackrel{(a)}{\preceq} \EBB[L_{t}^{-\frac{1}{2}}\tilde{H}_sL_t^{-1}\tilde{H}_sL_{t}^{-\frac{1}{2}}|\FM_{s-1}],
\end{align*}

where $(a)$ follows from the fact that for any random matrix $X$: $\EBB[(X-\EBB[X])X-\EBB[X])^\top]\preceq \EBB[XX^\top].$ Continuing

\begin{align*}
&\EBB[L_{t}^{-\frac{1}{2}}\tilde{H}_sL_t^{-1}\tilde{H}_sL_{t}^{-\frac{1}{2}}|\FM_{s-1}] \\
&= L_t^{-1/2}\tilde{A}_{s-1}^{1/2} \EBB[4d^4f_s(y_s)^2(v_{s,1}v_{s,2}^\top +v_{s,2}v_{s,1}^\top )\tilde{A}_{s-1}^{1/2} L_t^{-1}\tilde{A}_{s-1}^{1/2}(v_{s,1}v_{s,2}^\top +v_{s,2}v_{s,1}^\top )|\FM_{s-1}]\tilde{A}_{s-1}^{1/2} L_t^{-1/2}\\
&\stackrel{(a)}{\preceq} L_t^{-1/2}\tilde{A}_{s-1}^{1/2} \EBB[6d^4f_s(y_s)^2(v_{s,1}v_{s,2}^\top +v_{s,2}v_{s,1}^\top )(v_{s,1}v_{s,2}^\top +v_{s,2}v_{s,1}^\top )|\FM_{s-1}]\tilde{A}_{s-1}^{1/2} L_t^{-1/2},\\
&\stackrel{(b)}{\preceq} 6d^4(B^*)^2 \kappa L_t^{-1/2}\tilde{A}_{s-1}^{1/2} \EBB[(v_{s,1}v_{s,2}^\top +v_{s,2}v_{s,1}^\top )(v_{s,1}v_{s,2}^\top +v_{s,2}v_{s,1}^\top )|\FM_{s-1}]\tilde{A}_{s-1}^{1/2} L_t^{-1/2},
\end{align*}

where $(a)$ follows from the fact that $\tilde{A}_{s-1}^{1/2} L_t^{-1}\tilde{A}_{s-1}^{1/2} \preceq 1.5\kappa I$ w.h.p, and $(b)$ follows from the fact that $f_s(y_s) \leq B^*$. Next, we rely on the facts that $\EBB[v_{s,1}v_{s,2}^\top v_{s,1}v_{s,2}^\top] = d^{-2}I,$ and $\EBB[v_{s,1}v_{s,2}^\top v_{s,2}v_{s,1}^\top] = d^{-1}I$ to obtain

\begin{align*}
&\EBB[L_{t}^{-\frac{1}{2}}\tilde{H}_sL_t^{-1}\tilde{H}_sL_{t}^{-\frac{1}{2}}|\FM_{s-1}] \\
&\preceq 12d^3(B^*)^2(1+d^{-1})\kappa L_t^{-1/2}\tilde{A}_{s-1}L_t^{-1/2}\\
& \stackrel{(a)}{\preceq} 36d^3(B^*)^2\kappa^2,
\end{align*}

where $(a)$  follows from the fact that $ L_t^{-1/2}\tilde{A}_{s-1}L_t^{-1/2} \preceq 1.5\kappa I$ w.h.p.

Matrix Freedman. With the above bounds on the martingale sequence, we can bound $L_{t}^{-\frac{1}{2}}(A_{t} - \tilde{A}_{t})L_{t}^{-\frac{1}{2}}$ by matrix Freedman inequality (Lemma <ref>) [Freedman's inequality requires the first and second moment bounds to hold almost surely. Observe that we only have these bounds in high probability. However, there is a standard workaround to this, as shown in Suggala et al., 2021, where one can create an alternate martingale that satisfies these bounds a.s., and is exactly equal to the original martingale w.h.p.]

\begin{align*}
\|I-\tilde{A}_{t}^{-\frac{1}{2}}A_t\tilde{A}_{t}^{-\frac{1}{2}}\|_2 &\leq \|L_{t}^{-\frac{1}{2}}(A_{t} - \tilde{A}_{t})L_{t}^{-\frac{1}{2}}\|_2 \\
& \leq \frac{12\eta \kappa d^{3/2}B^*\sqrt{t\log(dT^2)}}  {\kappa'} + \frac{8\eta \kappa d^2B^*\log(dT^2)}{\kappa'}.
\end{align*}

The RHS of the above inequality is less than $1/2$ for our choice of $\eta$.

Let $\tilde{A}_t=\tilde{A}_{t-1}+\frac{\eta}{\kappa'}\tilde{H}_{t}$, and $A_{t}=A_{t-1}+\frac{\eta}{\kappa'}H_t$, where $A_0=\tilde{A}_{0}=I$. Let $B^*=B+\sqrt{2}(G+\sqrt{2}C)$. Suppose $\eta\le \min\{c,1\}\kappa'(2\sqrt{T}(C+6d^2B^*)\log(dT^2))^{-1}$, $\forall t$, with probability at least $1-\frac{t}{T^2}$, for every $s\le t$,

\begin{align*}
\|I-A_{s}^{-\frac{1}{2}}\tilde{A}_sA_{s}^{-\frac{1}{2}}\|_2\le \frac{1}{2}.
\end{align*}

First observe that using Stokes' theorem [Flaxman et al., 2004], we have

\[
\E[\tilde{H}_t\mid \FM_{t-1}] = \nabla^2 \smoothfBB{t}(x_t),
\]

where $\FM_t$ denotes the filtration generated by $\{v_{s,1},v_{s,2}\}_{s=1}^{t}$, and

\[
\smoothfBB{t}(x) \coloneqq \E_{u\sim \ball, v \sim \ball}\left[f_t\left(x + \frac{1}{2} \tilde{A}_{t-1}^{-\frac{1}{2}}(u+v)\right)\right].
\]

We now prove the Lemma by induction. Base case $t=0$ is given by construction. Suppose the inequalities hold with probability at least $1-\frac{t-1}{T^2}$ for any $0\le s\le t-1$. Recall that $f_t$ is assumed to be be bounded by $B$ and $G$-Lipschitz over $\K$ and $C$-smooth. Note that $|f_t(y_t)|$ is bounded by

\begin{align*}
|f_t(y_t)|&\le |f_t(x_t)|+\left|f_t\left(x_t+\frac{1}{2}\tilde{A}_{t-1}^{-\frac{1}{2}}(v_{t,1}+v_{t,2})\right)-f_t(x_t)\right|\\
&\le B +  \left\|\nabla f_t\left(x_t+\frac{1}{2}\tilde{A}_{t-1}^{-\frac{1}{2}}(v_{t,1}+v_{t,2})\right)\right\|_2 \left\|\frac{1}{2}\tilde{A}_{t-1}^{-\frac{1}{2}}(v_{t,1}+v_{t,2})\right\|_2\\
&\le B+\left(G+C\left\|\frac{1}{2}\tilde{A}_{t-1}^{-\frac{1}{2}}(v_{t,1}+v_{t,2})\right\|_2\right)\left\|\frac{1}{2}\tilde{A}_{t-1}^{-\frac{1}{2}}(v_{t,1}+v_{t,2})\right\|_2\\
&\le B+(G+C\|\tilde{A}_{t-1}^{-\frac{1}{2}}\|_2)\|\tilde{A}_{t-1}^{-\frac{1}{2}}\|_2.
\end{align*}

By induction hypothesis, with probability at least $1-\frac{t-1}{T^2}$, $\tilde{A}_{t-1}\succeq \frac{1}{2}A_{t-1}\succeq \frac{1}{2}I$, and thus the above inequality implies $|f_t(y_t)|\le B+\sqrt{2}\left(G+\sqrt{2}C\right)=:B^*$. Note that

\begin{align*}
cI-A_{t}^{-\frac{1}{2}}\tilde{A}_tA_{t}^{-\frac{1}{2}}&\preceq \frac{\eta}{\kappa'} \sum_{s=1}^t A_{t}^{-\frac{1}{2}}\left(\E[\tilde{H}_s\mid \FM_{s-1}]-\tilde{H}_s\right)A_{t}^{-\frac{1}{2}}\\
&\preceq\frac{\eta}{\kappa'}  \left(\sum_{s=1}^tZ_s\right),
\end{align*}

\begin{align*}
CI-A_{t}^{-\frac{1}{2}}\tilde{A}_tA_{t}^{-\frac{1}{2}}&\succeq \frac{\eta}{\kappa'} \sum_{s=1}^t A_{t}^{-\frac{1}{2}}\left(\E[\tilde{H}_s\mid \FM_{s-1}]-\tilde{H}_s\right)A_{t}^{-\frac{1}{2}}\\
&\succeq \frac{\eta}{\kappa'}  \left(\sum_{s=1}^tZ_s\right),
\end{align*}

where $Z_s=A_t^{-\frac{1}{2}}(\E[\tilde{H}_s\mid \FM_{s-1}]-\tilde{H}_s)A_t^{-\frac{1}{2}}$ forms a martingale sequence with respect to the filtration $\FM_{s}$. We have thus

\begin{align*}
\frac{\eta}{\kappa'}\left(\sum_{s=1}^tZ_s\right)-\max\{C-1,0\}I\preceq I-A_{t}^{-\frac{1}{2}}\tilde{A}_tA_{t}^{-\frac{1}{2}}\preceq \frac{\eta}{\kappa'}\left(\sum_{s=1}^tZ_s\right)+\max\{1-c,0\}I.
\end{align*}

Note that for symmetric matrices $A,B,C$ satisfying $C\preceq A\preceq B$, we have $\|A\|_2\le \max\{\|B\|_2,\|C\|_2\}$. Thus, we focus on bounding the spectral norm of $\sum_{s=1}^t Z_s$.

By definition of $\tilde{H}_t$, since $-2I\preceq v_{t,1}v_{t,2}^{\top}+v_{t,2}v_{t,1}^{\top}\preceq 2I$,

\begin{align*}
-4d^2B^*\tilde{A}_{t-1}\preceq \tilde{H}_t\preceq 4d^2B^*\tilde{A}_{t-1}.
\end{align*}

Thus, with probability at least $1-\frac{t-1}{T^2}$, $\forall s\le t$,

\begin{align*}
Z_s\preceq A_t^{-\frac{1}{2}}(CI+4d^2B^*\tilde{A}_{s-1})A_t^{-\frac{1}{2}}\preceq C I + 4d^2B^* A_{s-1}^{-\frac{1}{2}}\tilde{A}_{s-1}A_{s-1}^{-\frac{1}{2}}\preceq (C + 6d^2B^*) I,
\end{align*}

\begin{align*}
Z_s\succeq A_t^{-\frac{1}{2}}\left(-4d^2B^*\tilde{A}_{s-1}\right)A_t^{-\frac{1}{2}}\succeq -4d^2B^*A_{s-1}^{-\frac{1}{2}}\tilde{A}_{t}A_{s-1}^{-\frac{1}{2}}\succeq -6d^2B^*I.
\end{align*}

With the bound on the martingale sequence, we use matrix Azuma
inequality (Lemma <ref>).
By matrix Azuma’s inequality, assuming the inequality holds for $s\le t - 1$, with probability at least $1-\frac{1}{T^2}$,

\begin{align*}
\left\|I-A_{t}^{-\frac{1}{2}}\tilde{A}_tA_{t}^{-\frac{1}{2}}\right\|_2&\le \max\{C-1, 1-c, 0\}+\frac{4\eta}{\kappa'}\sqrt{t\log(dT^2)}(C+6d^2B^*)\\
&\le \max\{C, 2\}.
\end{align*}

Consider a self-adjoint matrix martingale $\{Y_k\}_{k\ge 0}$ of dimension $d$. Let $\{X_k\}_{k\ge 1}$ be the difference sequence of $\{Y_k\}_{k\ge 0}$. Assume that the difference sequence is uniformly bounded almost surely: $\exists R$ such that

\begin{align*}
\lambda_{\max}(X_k)\le R \ \ \ \text{almost surely} \ \ \ \forall k.
\end{align*}

Define the predictable quadratic variation process

\begin{align*}
W_k=\sum_{j=1}^k \E[X_j^2\mid\F_{j-1}], \ \ \ \forall k.
\end{align*}

Then $\forall \eps\ge 0, \sigma^2>0$,

\begin{align*}
\mathbb{P}\left(\exists k\ge 0: \lambda_{\max}(Y_k)\ge \eps \  \text{and }\|W_k\|_2\le \sigma^2\right)\le d\cdot\exp\left(-\frac{\eps^2/2}{\sigma^2+R\eps/3}\right).
\end{align*}

Let $B^* = B+\sqrt{2}(L+\sqrt{2}C)$. With probability at least $1-\frac{1}{T}$, the $y_t$ played by Algorithm <ref> satisfies

\begin{align*}
|f_t(y_t)|\le B^*, \ \forall t\in[T].
\end{align*}

Note that in the proof of Lemma <ref>, we have shown that $|f_t(y_t)|\le B^*$ if $\|I-A_{t-1}^{-\frac{1}{2}}\tilde{A}_{t-1}A_{t-1}^{-\frac{1}{2}}\|_2\le \frac{1}{2}$. Thus,

\begin{align*}
\mathbb{P}\left(|f_t(y_t)|\le B^*, \ \forall t\in[T]\right)\ge \mathbb{P}\left(\|I-A_{t}^{-\frac{1}{2}}\tilde{A}_{t}A_{t}^{-\frac{1}{2}}\|_2\le \frac{1}{2}, \ \forall t\in[T]\right)\ge 1-\frac{1}{T}.
\end{align*}

§.§ Proof of Theorem <ref>

Let $\ball = \{x:\|x\|_2 \leq 1\}, \sphere=\{x:\|x\|_2 = 1\}$ be the unit ball and unit sphere in $\mathbb{R}^d$. We define smoothed functions $\smoothfBB{t}, \smoothfBS{t}, \smoothfSS{t}$ as follows

\begin{align*}
&\smoothfBB{t}(x) \coloneqq \E_{u\sim \ball, v \sim \ball}\left[f_t\left(x + \frac{1}{2} \tilde{A}_{t-1}^{-\frac{1}{2}}(u+v)\right)\Big| \FM_{t-1}\right]\\
&\smoothfBS{t}(x) \coloneqq \E_{u\sim \ball, v \sim \sphere}\left[f_t\left(x + \frac{1}{2} \tilde{A}_{t-1}^{-\frac{1}{2}}(u+v)\right)\Big| \FM_{t-1}\right]\\
&\smoothfSS{t}(x) \coloneqq \E_{u\sim \sphere, v \sim \sphere}\left[f_t\left(x + \frac{1}{2} \tilde{A}_{t-1}^{-\frac{1}{2}}(u+v)\right)\Big| \FM_{t-1}\right].
\end{align*}

Observe that

\begin{align*}
\E[f_t(y_t)\mid \FM_{t-1}]=\smoothfSS{t}(x_t),
\end{align*}

where $\FM_t$ denotes the filtration generated by $\{v_{s,1},v_{s,2}\}_{s=1}^{t}$.

By Stokes' theorem [Flaxman et al., 2004], we have that the gradient and Hessian estimators constructed in Algorithm <ref> satisfy

\begin{align*}
&\E[\tilde{\nabla}_t\mid \FM_{t-1}] = \nabla \smoothfBS{t}(x_t),\quad \E[\tilde{H}_t\mid \FM_{t-1}] = \nabla^2 \smoothfBB{t}(x_t).
\end{align*}

Observe that the Hessian and gradients estimated in Algorithm <ref> are not of the same function. Interestingly, despite this mismatch, we can derive $\sqrt{T}$ regret of the algorithm. Define $A_t \coloneqq A_{t-1} + \frac{\eta}{\kappa'} \nabla^2\smoothfBB{t}(x_t)$, with $A_0=I$. Throughout the proof, we assume that the cumulative Hessian concentrates well; that is, the following holds

$$\|A_t^{-\frac{1}{2}}(A_t - \tilde{A}_t)A_t^{-\frac{1}{2}}\|_2 \leq \frac{1}{2}.$$

This assumption is formally proved in Lemma <ref>, which says that the above stated inequality holds simultaneously for all $t\in[T]$ with probability at least $1-\frac{1}{T}$. Therefore, we can without loss of generality assume that the above inequality holds deterministically by suffering an additional constant in the regret bound.

For any $x \in \K$, we can decompose the regret as the following:

\begin{align*}
\sum_{s=1}^{T}\E[f_s(y_s) -  f_s(x)] & = \sum_{s=1}^{T}\E[\smoothfSS{s}(x_s) -  f_s(x)]\\
& = \sum_{s=1}^{T}\E[\smoothfBS{s}(x_s) -  f_s(x)] + \E[\smoothfSS{s}(x_s) - \smoothfBS{s}(x_s)]\\
& =  \underbrace{\sum_{s=1}^{T}\E[\smoothfBS{s}(x_s) -  \smoothfBS{s}(x)]}_{T_1}  +  \underbrace{\sum_{s=1}^{T}\E[\smoothfBS{s}(x) -  f_s(x)]}_{T_2} +  \underbrace{\sum_{s=1}^{T}\E[\smoothfSS{s}(x_s) - \smoothfBS{s}(x_s)]}_{T_3} ,
\end{align*}

where we will bound $T_1,T_2$, and $T_3$ separately.

Bounding $T_1$. To bound this term, we rely on Lemma <ref>. In particular, we  instantiate it with the ONS algorithm described in  Algorithm <ref>, and use $\Tilde{\Delta}_t, \tilde{H}_t$ as the stochastic estimates of $\nabla \smoothfBS{t}(x_t), \nabla^2 \smoothfBS{t}(x_t)$. This gives us the following bound

\begin{align*}
T_1 \leq \frac{\text{diam}(\K)^2}{2\eta} + \sum_{t=1}^T \frac{\eta}{2} \EBB\left[\norm{\tilde{\nabla}_t}_{\tilde{A}_t^{-1}}^2\right] - \sum_{t=1}^T\EBB\left[\Delta_t(x)\right],
\end{align*}

where $\Delta_t(x)$ is defined as

\[
\Delta_t(x) \coloneqq \smoothfBS{t}(x) - \smoothfBS{t}(x_t) - \inp{\nabla \smoothfBS{t}(x_t)}{x-x_t} -  \frac{1}{2\kappa'}(x-x_t)^{\top}\EBB[\tilde{H}_t|\FM_{t-1}] (x-x_t).
\]

For our choice of $\kappa' (\ge \kappa)$, and our assumption on the Hessian of $f_t$, $\Delta_t(x)$ is always greater than $0$. This is because

\begin{align*}
\smoothfBS{t}(x) - \smoothfBS{t}(x_t) - \inp{\nabla \smoothfBS{t}(x_t)}{x - x_t}&\ge \frac{c}{2}\|x-x_{t}\|_{H_t}^2\ge \frac{1}{2\kappa'}(x-x_t)^\top \EBB[\tilde{H}_t|\FM_{t-1}](x-x_t).
\end{align*}

Next, we bound $\norm{\tilde{\nabla}_t}_{\tilde{A}_t^{-1}}$:

\begin{align*}
\norm{\tilde{\nabla}_t}_{\tilde{A}_t^{-1}}^2&=2d^2f_t(y_t)^2 v_{t,1}^{\top} \tilde{A}_{t-1}^{\frac{1}{2}}\tilde{A}_{t}^{-1}\tilde{A}_{t-1}^{\frac{1}{2}}v_{t,1}\\
&\stackrel{(a)}{\le} 6d^2f_t(y_t)^2v_{t,1}^{\top}A_{t-1}^{\frac{1}{2}}A_{t}^{-1}A_{t-1}^{\frac{1}{2}}v_{t,1}\\
&\stackrel{(b)}{\le} 6d^2(B^*)^2,
\end{align*}

where $(a)$ follows from the fact that $\frac{1}{2}A_t\preceq \tilde{A}_{t} \preceq \frac{3}{2}A_t$, and $(b)$ follows from Corollary <ref>. Substituting this in the above upper bound for $T_1$ gives us

\[
T_1 \leq \frac{\text{diam}(\K)^2}{2\eta} + 3\eta d^2(B^*)^2 T.
\]

Bounding $T_2$.
We now upper bound $T_2$ by $\tilde{O}(\frac{1}{\eta}).$ To see this, consider the following

\begin{align*}
T_2 &= \sum_{t=1}^T\E[\smoothfBS{t}(x) -  f_t(x)] \\
&= \sum_{t=1}^T\E_{u_t\sim \ball, v_t\sim \sphere}\left[f_t\left(x + \frac{1}{2}\tilde{A}_{t-1}^{-\frac{1}{2}}(u_t+v_t)\right) -  f_t(x)\right] \\
& = \sum_{t=1}^T\E_{u_t\sim \ball, v_t\sim \sphere}\left[\frac{1}{2}\nabla f_t(x)^{\top}\tilde{A}_{t-1}^{-\frac{1}{2}}(u_t+v_t)+\frac{1}{8}(u_t+v_t)^{\top}\tilde{A}_{t-1}^{-\frac{1}{2}}\nabla^2 f_t(x(u_t,v_t))\tilde{A}_{t-1}^{-\frac{1}{2}}(u_t+v_t)\right] \\
& = \frac{1}{8}\sum_{t=1}^T \E_{u_t\sim \ball, v_t\sim \sphere}[(u_t+v_t)^T\tilde{A}_{t-1}^{-\frac{1}{2}}\nabla^2f_t(x(u_t, v_t)) \tilde{A}_{t-1}^{-\frac{1}{2}}(u_t+v_t)],
\end{align*}

where the last equality follows from the fact that conditioning on $\FM_{t-1}$, the first-order term vanishes. Here, $x(u_t,v_t)$ is a point on the line connecting $x$ and $x + \frac{1}{2}\tilde{A}_{t-1}^{-\frac{1}{2}}(u_t+v_t)$. Next, observe that $\nabla^2f_t(x(u_t, v_t)) \preceq C H_t \preceq \frac{C}{c}\E[\tilde{H}_t\mid \FM_{t-1}] \preceq \kappa \E[\tilde{H}_t\mid \FM_{t-1}]$. Substituting this in the previous display gives us

\begin{align*}
T_2  & \leq \frac{\kappa}{8}\sum_{t=1}^T \E[(u_t+v_t)^T\tilde{A}_{t-1}^{-\frac{1}{2}}\E[\tilde{H}_t\mid \FM_{t-1}] \tilde{A}_{t-1}^{-\frac{1}{2}}(u_t+v_t)].
\end{align*}

Next, since by concentration of Hessian estimate accumulates, we have $\tilde{A}_t\succeq \frac{1}{2}A_t$ and the fact that

\begin{align*}
A_{t-1}=A_t- \frac{\eta}{\kappa'} \E[\tilde{H}_t\mid \FM_{t-1}]\succeq A_t-c\eta I\succeq \frac{1}{2}A_t,
\end{align*}

we bound $T_2$ as

\begin{align*}
T_2 &\leq  \frac{\kappa}{4}\sum_{t=1}^T \E[(u_t+v_t)^{\top}A_{t-1}^{-\frac{1}{2}}\E[\tilde{H}_t\mid \FM_{t-1}] A_{t-1}^{-\frac{1}{2}}(u_t+v_t)]\\
&\leq  \frac{\kappa}{2}\sum_{t=1}^T \E[(u_t+v_t)^{\top}A_{t}^{-\frac{1}{2}}\E[\tilde{H}_t\mid \FM_{t-1}] A_{t}^{-\frac{1}{2}}(u_t+v_t)].
\end{align*}

Continuing, we have with $|\cdot|$ denoting the determinant of a square matrix,

\begin{align*}
T_2 & \le \frac{\kappa\kappa'}{2\eta }\sum_{t=1}^T \E[(u_t+v_t)^{\top}A_{t}^{-\frac{1}{2}} (A_{t} - A_{t-1}) A_{t}^{-\frac{1}{2}}(u_t+v_t)]\\
& = \frac{\kappa\kappa'}{\eta}\sum_{s=1}^T \E[\trace(A_{t}^{-\frac{1}{2}} (A_{t} - A_{t-1}) A_{t}^{-\frac{1}{2}})]\\
& \stackrel{(c)}{\le} \frac{\kappa\kappa'}{\eta}\E\left[\log\frac{|A_T|}{|A_0|}\right] \\
& \stackrel{(d)}{\le} \frac{\kappa\kappa' d\log(1+ \eta C T/\kappa')} {\eta},
\end{align*}

where inequality $(c)$ follows
from the fact that for $A,B\succeq 0$,

$$A^{-1}\cdot (A-B)\le \log\frac{|A|}{|B|},$$

and inequality $(d)$ follows from the fact that the since the largest eigenvalue $\lambda_{\max}(A_T)$ of $A_T$ satisfies $\lambda_{\max}(A_T)\le 1+ \eta CT/\kappa'$,

\begin{align*}
\log |A_T|\le \log\left(\lambda_{\max}(A_T)^d\right)\le d \log(1+\eta CT/\kappa').
\end{align*}

Bounding $T_3$.

\begin{align*}
T_3 &= \sum_{s=1}^{T}\E[\smoothfSS{s}(x_s) - \smoothfBS{s}(x_s)]\\
& \stackrel{(a)}{\leq} \sum_{s=1}^{T}\E[\smoothfSS{s}(x_s) - f_s(x_s)],
\end{align*}

where $(a)$ follows from the convexity of $f_s$:

\begin{align*}
\smoothfBS{s}(x_s) &= \EBB_{u_s\sim \ball, v_s\sim \sphere}\left[f_s\left(x_s+\frac{1}{2}\tilde{A}_{t-1}^{-\frac{1}{2}}(u_s+v_s)\right)\right] \geq f_s\left(x_s + \frac{1}{2}\EBB_{u_s\sim \ball, v_s\sim \sphere}\left[\tilde{A}_{t-1}^{-\frac{1}{2}}(u_s+v_s)\right]\right)\\
& = f_s(x_s)
\end{align*}

Using similar arguments as $T_2$ to bound $\E[\smoothfSS{s}(x_s) - f_s(x_s)]$, we obtain

\begin{align*}
T_3 \leq  \frac{\kappa\kappa' d\log(1+ \eta C T/\kappa')} {\eta}.
\end{align*}

Combining the bounds for $T_1, T_2, T_3$ gives us the required regret bound.

§ REGRET OF BANDIT NEWTON METHOD FOR PROPER LEARNING (SECTION <REF>)

§.§ Properties of Iterates

Define the smoothed function $\smoothfBB{t}$ as

\smoothfBB{t}(x) \coloneqq \E_{u\sim \ball, v \sim \ball}\left[f_t\left(x + \frac{1}{4} \tilde{A}_{t}^{-\frac{1}{2}}(u+v)\right)\right].

Let $\tilde{A}_t=\nabla^2R(x_t)+\frac{\eta}{\kappa'}\sum_{s=0}^{t-1}\tilde{H}_{s}$, and $A_t=\nabla^2R(x_t)+\frac{\eta}{\kappa'}\sum_{s=0}^{t-1}\nabla^2\smoothfBB{s}(x_s)$.

Suppose $\eta\le \kappa'(12d^2B\sqrt{T})\log(dT^2))^{-1}$. Then, $\forall t$, with probability at least $1-\frac{t}{T^2}$, the following properties holds for every $s\le t$,

* $\tilde{A}_s$ is close to $A_s$

\begin{align*}
\|I-A_{s}^{-\frac{1}{2}}\tilde{A}_sA_{s}^{-\frac{1}{2}}\|_2\le \frac{1}{2}.
\end{align*}

* $y_s$ lies in the constraint set $\K$

We prove the result using induction.

Base case ($t=1$). Since $\tilde{A}_1 = A_1 = \nabla^2R(x_1)$, the first part holds trivially. Using Dikin Ellipsoid property of SCBs, we can also conclude that $y_1 \in \K$.

Induction Step. Suppose the hypothesis holds with probability at least $1-\frac{t-1}{T^2}$ for any $0\le s\le t-1$. We show that the properties hold at iteration $t$.

Consider the following

\begin{align*}
A_t^{-1/2}(A_t-\tilde{A}_t)A_t^{-1/2}&=\frac{\eta}{\kappa'} \sum_{s=1}^t A_{t}^{-\frac{1}{2}}(\E[\tilde{H}_s\mid \F_{s-1}]-\tilde{H}_s)A_{t}^{-\frac{1}{2}},
\end{align*}

where $Z_s=A_{t}^{-\frac{1}{2}}(\E[\tilde{H}_s\mid \F_{s-1}]-\tilde{H}_s)A_{t}^{-\frac{1}{2}}$ forms a martingale sequence with respect to the filtration $\F_{s}$. Here, we used the fact that $\E[\tilde{H}_s\mid \F_{s-1}] = \nabla^2\smoothfBB{s}(x_s).$ Furthermore, note that by definition of $\tilde{H}_s$, since $-2I\preceq v_{t,1}v_{t,2}^{\top}+v_{t,2}v_{t,1}^{\top}\preceq 2I$, we have

\begin{align*}
\forall s \le t-1, \quad -16d^2B\tilde{A}_{s}\preceq \tilde{H}_s\preceq 16d^2B\tilde{A}_{s}.
\end{align*}

Thus, with probability at least $1-\frac{t-1}{T^2}$, $\forall s\le t-1$,

\begin{align*}
Z_s\preceq A_{t}^{-\frac{1}{2}}\left(32d^2B\tilde{A}_{s}\right)A_{t}^{-\frac{1}{2}}\preceq \textcolor{red}{32d^2B A_{s}^{-\frac{1}{2}}\tilde{A}_{s}A_{s}^{-\frac{1}{2}}},
\end{align*}

\begin{align*}
Z_s\succeq A_t^{-\frac{1}{2}} \left(-16d^2B^*\tilde{A}_{s-1}\right) A_t^{-\frac{1}{2}}\succeq \textcolor{red}{-16d^2B^* A_{s-1}^{-\frac{1}{2}}\tilde{A}_{s-1}A_{s-1}^{-\frac{1}{2}}}.
\end{align*}

We need some relation between $A_s$ and $A_t$ that can help us bound $A_t^{-1/2}A_s^{1/2}$.

Is it possible if we take $A_t=\max_{t\in[T]}\nabla^2 R(x_t)+\sum_{s=0}^{t-1}\nabla^2 \tilde{f}_{s}^{\ball,\ball}(x_s)$?

§.§ Proof of Theorem <ref>

Similar to the proof of Theorem <ref>, we first define the following smoothed functions

\begin{align*}
&\smoothfBB{t}(x) \coloneqq \E_{u\sim \ball, v \sim \ball}\left[f_t\left(x + \frac{1}{2} \tilde{A}_{t-1}^{-\frac{1}{2}}(u+v)\right)\right]\\
&\smoothfBS{t}(x) \coloneqq \E_{u\sim \ball, v \sim \sphere}\left[f_t\left(x + \frac{1}{2} \tilde{A}_{t-1}^{-\frac{1}{2}}(u+v)\right)\right]\\
&\smoothfSS{t}(x) \coloneqq \E_{u\sim \sphere, v \sim \sphere}\left[f_t\left(x + \frac{1}{2} \tilde{A}_{t-1}^{-\frac{1}{2}}(u+v)\right)\right].
\end{align*}

Observe that

\begin{align*}
\E[f_t(y_t)\mid \F_{t-1}]=\smoothfSS{t}(x_t),
\end{align*}

where $\F_t$ denotes the filtration generated by $\{v_{s,1},v_{s,2}\}_{s=1}^{t}$.

By Stokes' theorem [Flaxman et al., 2004], we have that the gradient and Hessian estimators constructed in Algorithm <ref> satisfy

\begin{align*}
&\E[\tilde{\nabla}_t\mid \F_{t-1}] = \nabla \smoothfBS{t}(x_t),\quad \E[\tilde{H}_t\mid \F_{t-1}] = \nabla^2 \smoothfBB{t}(x_t).
\end{align*}

Throughout the proof we assume that the cumulative Hessian concentrates well around the true cumulative Hessian:

\begin{align*}
\forall s\in [T], \ \|I-A_{s}^{-\frac{1}{2}}\tilde{A}_sA_{s}^{-\frac{1}{2}}\|_2\le \frac{1}{2}.
\end{align*}

Let $A_t = \left(\nabla^2 R(x_t) + \sum_{s=0}^{t-1}\eta/\kappa' \nabla^2\smoothfBB{s}(x_s)\right).$
For any $t \leq T$

\begin{align*}
\|x_{t+1}-x_t\|_{A_{t}} = O(\eta\|\nabla \smoothfBS{t}(x_t)\|_{A_t}^*).
\end{align*}

Recall, $x_{t+1}$ is the minimizer of the following objective

\[
x_{t+1} = \argmin_{x\in \K} \eta\left\langle\tilde{\nabla}_t, x\right\rangle + \bregt{t+1}(x,x_{t})
\]

From the first order optimality conditions, we have

\begin{align}
\label{eqn:xt_opt_condition}
\forall x \in \K, \quad \iprod{\nabla R_{t+1}(x_{t+1}) -\nabla R_{t+1}(x_{t})  + \eta\nabla \smoothfBS{t}(x_t)}{x-x_{t+1}} \geq 0.
\end{align}

Replacing $x$ in the above equation with $x_t$ and rearranging terms gives us

\begin{align*}
\iprod{\nabla R(x_{t+1}) -\nabla R(x_{t}) +  \eta\nabla \smoothfBS{t}(x_t) + \sum_{s=1}^{t}\frac{\eta}{\kappa'} H_s(x_{t+1}-x_{t})}{x_{t+1}-x_{t}} \leq 0.
\end{align*}

Now suppose $\|x_{t+1}-x_{t}\|_{A_{t}} > \eta\|\nabla \smoothfBB{t}(x_t)\|_{A_t}^*$. Then we have

\begin{align*}
&\iprod{\nabla R(x_{t+1}) -\nabla R(x_t)  + \eta \nabla f_t(x_t) + \sum_{s=1}^t\eta H_s(x_{t+1}-x_t)}{x_{t+1}-x_t} \\
&\quad \stackrel{(a)}{\geq}  \frac{\|x_{t+1}-x_t\|_{\nabla^2R(x_t)}^2}{1+\|x_{t+1}-x_t\|_{\nabla^2R(x_t)}} + \eta\|x_{t+1}-x_t\|_{H_{1:t}}^2 +  \iprod{\eta \nabla f_t(x_t)}{x_{t+1}-x_t}\\
&\quad \stackrel{(b)}{\geq} \frac{\|x_{t+1}-x_t\|_{\nabla^2R(x_t)}^2}{1+\|x_{t+1}-x_t\|_{\nabla^2R(x_t)}}  + \eta\|x_{t+1}-x_t\|_{H_{1:t}}^2- \eta \|\nabla f_t(x_t)\|^*_{A_t}\|x_{t+1}-x_t\|_{A_t},
\end{align*}

where $(a)$ follows from property P3 of SCBs stated in Appendix <ref> and $(b)$ follows from the fact that $H_t$ is a positive semi-definite matrix. Here $H_{1:t} = \sum_{s=1}^t H_{s}$. Continuing

\begin{align*}
&\iprod{\nabla R(x_{t+1}) -\nabla R(x_t)  + \eta \nabla f_t(x_t) + \sum_{s=1}^t\eta H_s(x_{t+1}-x_t)}{x_{t+1}-x_t} \\
&\quad \stackrel{(b)}{\geq} \frac{\|x_{t+1}-x_t\|_{A_t}^2}{1+\|x_{t+1}-x_t\|_{A_t}}  - \eta \|\nabla f_t(x_t)\|^*_{A_t}\|x_{t+1}-x_t\|_{A_t},
\end{align*}

Next, consider the following

Substituting this in the previous inequality and using the fact that $\|x_{t+1}-x_t\|_{A_t} > 2\lambda^{-1}dB\eta_t$ gives us

\begin{align*}
&\iprod{\nabla R(\x_{t+1}) -\nabla R(\x_t)  + \eta_t \gest{t} + \sum_{s=1}^t\eta_s \hest{s}(\x_{t+1}-\x_t)}{\x_{t+1}-\x_t} \\
&\quad \geq \lambda^{-1}dB\eta_t\|\x_{t+1}-\x_t\|_{M_t} \left(\frac{2}{1+2\lambda^{-1}dB\eta_t} -  1 \right)\\
&\quad \stackrel{(a)}{>} 0,
\end{align*}

where $(a)$ follows from the fact that $\lambda^{-1}dB\eta_t < 1/2.$  This contradicts the first order optimality condition in Equation (<ref>).
This shows that $\|\x_{t+1}-\x_t\|_{M_t} \leq 2\lambda^{-1}dB\eta_t.$

For any $t \leq T,$ and any $x\in \K$

$$\iprod{\tilde{\nabla}_{t}}{x_{t+1}-x} \leq \frac{\|x-x_t\|^2_{A_t} - \|x-x_{t+1}\|^2_{A_t}}{2\eta}$$

Observe that $x_{t+1}$ can be rewritten as

\[
x_{t+1} = \argmin_{x\in \K} \|x-(x_t-\eta A_t^{-1}\tilde{\nabla}_{t})\|_{A_t}^2.
\]

From first order optimality conditions, we have the following for any $x\in \K$

\begin{align*}
\iprod{x_{t+1} - x_t + \eta A_t^{-1}\tilde{\nabla}_{t}}{x-x_{t+1}}_{A_t} \geq 0
\end{align*}

Rearranging terms in the above inequality gives us the required result.

§ REGRET OF BANDIT NEWTON METHOD FOR BQO-AM (SECTION <REF>)

We first make two observations on Algorithm <ref>. Algorithm <ref> does improper learning, as the decisions $y_t$'s do not necessarily lie within $\K$. We bound the function value and gradient evaluated at $y_t$'s in Remark <ref>. The dependence of the iterates are explained in Remark <ref>.

Since Algorithm <ref> does improper learning, it is essential to show that the loss and gradient at each of the $y_t$ played by the algorithm is bounded. Note that $\forall t$,

\begin{align*}
\|\nabla f_t(y_{t-m+1:t})\|_2&\le \|\nabla f_t(x_{t-m+1:t})\|_2+\beta \|y_{t-m+1:t}-x_{t-m+1:t}\|_2\le L+\beta \sqrt{m}, \\
|f_t(y_{t-m+1:t})|&\le |f_t(x_{t-m+1:t})|+|\nabla f_t(y_{t-m+1:t})^{\top}(y_{t-m+1:t}-x_{t-m+1:t})| \\
&\le B+(L+\beta\sqrt{m})\sqrt{m}.
\end{align*}

We denote $B^*=B+(L+\beta\sqrt{m})\sqrt{m}$.

Denote $\F_t=\sigma(\{u_s\}_{s\le t})$ to be the filtration generated by Algorithm <ref> random sampling step. Then by Assumption <ref>, $f_t, H_t, \hat{A}_t$ are $\F_{t-m}$-measurable. By the delayed updates in Algorithm <ref>, $x_t$ is $\F_{t-m}$-measurable. $u_t, y_t,\tilde{g}_t$ are $\F_t$-measurable.

We now prove Theorem <ref>.
Following usual procedure of bounding with-memory regret in bandit setting, we note that the regret can be decomposed into three terms, which we will bound separately:

\begin{align*}
\E[\regret_T(x)]&=\underbrace{\E\left[\sum_{t=m}^T f_t(y_{t-m+1:t})-f_t(x_{t-m+1:t})\right]}_{(\text{perturbation loss})}+\underbrace{\E\left[\sum_{t=m}^T f_t(x_{t-m+1:t})-\bar{f}_{t}(x_t)\right]}_{(\text{movement cost})}\\
& \ \ \ \ \ +\underbrace{\E\left[\sum_{t=m}^T \bar{f}_{t}(x_{t})-\bar{f}_{t}(x)\right]}_{(\text{underlying regret})}.
\end{align*}

We will decompose the proof as the following: First, we will show some useful properties of the gradient estimator $\tilde{g}_t$. Then, we will bound the three terms above separately.

§.§ Properties of the gradient estimator

$\forall t$, the conditional expectation of the gradient estimator is given by

\begin{align*}
\E[\tilde{g}_t\mid \F_{t-m}]=\sum_{i=1}^m [\nabla f_t(x_{t-m+1:t})]_i,
\end{align*}

where $[\nabla f_t(x_{t-m+1:t})]_i$ denotes the $i$-th $d$-vector in the $dm$-vector $\nabla f_t(x_{t-m+1:t})$.

The proof follows similarly to the proof of Lemma C.3 in [Sun et al., 2023]. In particular, we note that for a real-valued quadratic function on $\mathbb{R}^n$ $q(x)=\frac{1}{2}x^{\top} Ax+b^{\top}x+c$, a symmetric positive-definite matrix $M\in\mathbb{R}^{d\times d}$, a filtration $\F$, and a random unit vector $u\in\mathbb{R}^n$ satisfying (1) $u$ is symmetric with zero first and third moments conditioning on $\F$, (2) $u$ satisfies $\E[uu^{\top}\mid \F]=\frac{r}{n}I_{n\times n}$, and (3) $A, b, c, x$ are $\F$-measurable, then

\begin{align*}
\E\left[q(x+Mu)M^{-1}u\mid \F\right]&=\frac{1}{2}\E\left[(x+Mu)^{\top}A(x+Mu)M^{-1}u\mid \F\right]+\E\left[b^{\top}(x+Mu)M^{-1}u\mid \F\right]\\
& \ \ \ \ \ +\E[cM^{-1}u\mid \F]\\
&=\frac{1}{2}\E[x^{\top}AMuM^{-1}u\mid \F]+\frac{1}{2}\E[u^{\top}MAxM^{-1}u\mid \F]+\E[b^{\top}MuM^{-1}u\mid \F]\\
&=\frac{1}{2}M^{-1}\E[uu^{\top}\mid \F]MA^{\top}x+\frac{1}{2}M^{-1}\E[uu^{\top}\mid \F]MAx+M^{-1}\E[uu^{\top}\mid\F] Mb\\
&=\frac{r}{n}\nabla q(x).
\end{align*}

Consider the following matrix $M_t\in\mathbb{R}^{dm\times dm}$:

\begin{align*}
M_t =\begin{bmatrix}
\hat{A}_{t-m}^{-\frac{1}{2}} & 0 & \dots & 0 \\
0 & \hat{A}_{t-m+1}^{-\frac{1}{2}} & \dots & 0 \\
\dots & \dots & \dots & \dots \\
0 & 0 & \dots & \hat{A}_{t-1}^{-\frac{1}{2}}
\end{bmatrix}.
\end{align*}

By Remark <ref>, $f_t, M_t$ is $\F_{t-m}$-measurable, and the concatenated vector $v_t=[u_{t-m+1},\dots u_t]$ satisfies that the first and third moments of $v_t$ is $0$ conditioning on $\F_{t-m}$, and since $u_{t-m+1},\dots,u_t$ are independent conditioning on $\F_{t-m}$,

\begin{align*}
\E[v_t(v_t)^{\top}\mid \F_{t-m}]=\frac{1}{d}I_{dm\times dm}.
\end{align*}

By taking $r=m$, we have that

\begin{align*}
\nabla f_t(x_{t-m+1:t})=\E[df_t(y_{t-m+1:t})M_t^{-1}v_t\mid \F_{t-m}].
\end{align*}

We note that by definition of the gradient estimator $\tilde{g}_{t}$,

\begin{align*}
\sum_{i=1}^m [\nabla f_t(x_{t-m+1:t})]_i&=\E\left[df_t(y_{t-m+1:t})\sum_{i=1}^m [M_t^{-1}v_t]_i\mid \F_{t-m}\right]\\
&=\E\left[df_t(y_{t-m+1:t})\sum_{s=t-m+1}^t\hat{A}_{s}^{\frac{1}{2}}u_s\mid \F_{t-m}\right]\\
&=\E\left[\tilde{g}_{t}\mid \F_{t-m}\right].
\end{align*}

§.§ Bounding perturbation loss

We start with the perturbation loss and prove the following proposition:

The perturbation loss is bounded by

\begin{align*}
\E\left[\sum_{t=m}^T f_t(y_{t-m+1:t})-f_t(x_{t-m+1:t})\right]\le \beta R_G\left[\frac{10mR_GR_Y}{\kappa(G)}\sqrt{T} + \frac{4md\log(\sigma T) }{\eta\alpha\kappa(G)} +  dR_Y^2\sqrt{T}\right].
\end{align*}

Note that by the quadratic assumption on $f_t$, we have by second-order Taylor expansion:

\begin{align*}
\sum_{t=m}^T \E[f_t(y_{t-m+1:t})-f_t(x_{t-m+1:t})]&=\sum_{t=m}^T \E[\nabla f_t(x_{t-m+1:t})^{\top}\hat{A}_{t-m:t-1}^{-\frac{1}{2}}u_{t-m+1:t}]\\
& \ \ \ \ \ +\frac{1}{2} \sum_{t=m}^T \E[u_{t-m+1:t}^{\top}\hat{A}_{t-m:t-1}^{-\frac{1}{2}}\nabla^2 f_t \hat{A}_{t-m:t-1}^{-\frac{1}{2}}u_{t-m:1:t}].
\end{align*}

The first order term is $0$ since $\forall t$, since $f_t, x_{t-m+1},\dots, x_t, \hat{A}_{t-m},\dots,\hat{A}_{t-1}$ are $\F_{t-m}$-measurable,

\begin{align*}
\E[\nabla f_t(x_{t-m+1:t})^{\top}\hat{A}_{t-m:t-1}^{-\frac{1}{2}}u_{t-m+1:t}]=\E[\nabla f_t(x_{t-m+1:t})^{\top}\hat{A}_{t-m:t-1}^{-\frac{1}{2}}\E[u_{t-m+1:t}\mid \F_{t-m}]]=0.
\end{align*}

The second term can be bounded as following. Note that by denoting $[\nabla^2 f_t]_{ij}$ as the $ij$-th $d\times d$ block of $\nabla^2 f_t$, we have

\begin{align*}
u_{t-m+1:t}^{\top}\hat{A}_{t-m:t-1}^{-\frac{1}{2}}\nabla^2 f_t \hat{A}_{t-m:t-1}^{-\frac{1}{2}}u_{t-m+1:t}&=[\hat{A}_{t-m}^{-\frac{1}{2}}u_{t-m+1},\dots,\hat{A}_{t-1}^{-\frac{1}{2}}u_t]^{\top}\nabla^2 f_t[\hat{A}_{t-m}^{-\frac{1}{2}}u_{t-m+1},\dots,\hat{A}_{t-1}^{-\frac{1}{2}}u_t]\\
&=\sum_{i,j=1}^m u_{t-m+i}^{\top}\hat{A}_{t-m+i-1}^{-\frac{1}{2}}[\nabla^2 f_t]_{ij}\hat{A}_{t-m+j-1}^{-\frac{1}{2}}u_{t-m+j}.
\end{align*}

By independence between $u_s, u_t$ for $s\ne t$ and taking the expectation, we have

\begin{align*}
\E[u_{t-m+1:t}^{\top}\hat{A}_{t-m:t-1}^{-\frac{1}{2}}\nabla^2 f_t \hat{A}_{t-m:t-1}^{-\frac{1}{2}}u_{t-m:1:t}]&=\sum_{i=1}^m \E[u_{t-m+i}^{\top}\hat{A}_{t-m+i-1}^{-\frac{1}{2}}[\nabla^2 f_t]_{ii}\hat{A}_{t-m+i-1}^{-\frac{1}{2}}u_{t-m+i}]\\
&\le \sum_{i=1}^m \E\left[\trace(\hat{A}_{t-m+i-1}^{-\frac{1}{2}}[\nabla^2 f_t]_{ii}\hat{A}_{t-m+i-1}^{-\frac{1}{2}})\right]\\
&\le \E\left[\trace\left(\hat{A}_{t-m}^{-\frac{1}{2}}\sum_{i=1}^m [\nabla^2 f_t]_{ii}\hat{A}_{t-m}^{-\frac{1}{2}}\right)\right],
\end{align*}

where the last steps follow from that $\hat{A}_{s}\preceq \hat{A}_{t}$, $\forall s\le t$, and $\trace(\cdot)$ is linear. Note that since $f_t$ is quadratic, $[\nabla^2 f_t]_{ii}=\nabla^2_{y_{t-m+i}} f_t$, where $\nabla^2_{y_{t-m+i}} f_t$ is the Hessian of $f_t$ w.r.t. $y_{t-m+i}$. $\forall 1\le i\le m-1$, by smoothness assumption on $Q_t$,

\begin{align*}
[\nabla^2 f_t]_{ii}=\nabla^2_{y_{t-m+i}} f_t=Y_{t-m+i}^{\top}(G^{[m-i]})^{\top}Q_tG^{[m-i]}Y_{t-m+i}\preceq \beta\tilde{R}_{G}Y_{t-m+i}^{\top}Y_{t-m+i}.
\end{align*}

Denote $\sigma=\max_{t\in[T]}\lambda_{\max}(H_t)\le R_G^2R_Y^2$. For simplicity, assume that $\sigma\ge 1$ and $\eta\alpha\sigma m\le 2$, which will be satisfied by our choice of $\eta$ and $m$. Summing over all iterations, we have

\begin{align*}
\frac{1}{2} \sum_{t=m}^T \E[u_{t-m+1:t}^{\top}\hat{A}_{t-m:t-1}^{-\frac{1}{2}}\nabla^2 f_t \hat{A}_{t-m:t-1}^{-\frac{1}{2}}u_{t-m:1:t}]&\le \frac{1}{2}\sum_{t=m}^T \E\left[\trace\left(\hat{A}_{t-m}^{-\frac{1}{2}}\sum_{i=1}^m [\nabla^2 f_t]_{ii}\hat{A}_{t-m}^{-\frac{1}{2}}\right)\right]\\
&\le \frac{\beta\tilde{R}_{G}}{2}\sum_{t=m}^{T}\E\left[\trace\left(\hat{A}_{t-m}^{-\frac{1}{2}}\left(\sum_{s=t-m+1}^t Y_{s}^{\top}Y_{s}\right)\hat{A}_{t-m}^{-\frac{1}{2}}\right)\right]\\
&\le\beta\tilde{R}_{G}\sum_{t=m}^{T}\E\left[\trace\left(\hat{A}_{t}^{-\frac{1}{2}}\left(\sum_{s=t-m+1}^tY_{s}^{\top}Y_{s}\right) \hat{A}_{t}^{-\frac{1}{2}}\right)\right],
\end{align*}

where the third inequality follows from that since $\hat{A}_t\succeq mI$, $\forall t$, we have that $\forall s < t$,

\begin{align}
\label{eqn:preconditioner-inequality}
\hat{A}_t=\hat{A}_s+\frac{\eta\alpha}{2}\sum_{r=s+1}^t H_r\preceq \hat{A}_s+\frac{\eta\alpha\sigma m(t-s)}{2}I\preceq \left(1+\frac{\eta\alpha\sigma(t-s)}{2}\right)\hat{A}_s,
\end{align}

which implies that assuming $\eta\alpha\sigma m\le 2$, we have $\hat{A}_{t}\preceq \max\{2, \eta\alpha\sigma m\}\hat{A}_{t-m}\preceq 2\hat{A}_{t-m}$.

Here, we use a similar “blocking" technique used in [Simchowitz, 2020] to bound this term. In particular, for some $\tau\in\mathbb{Z}_{++}$ to be determined later (we will take $\tau=\lfloor\sqrt{T}\rfloor$), consider endpoints $k_j=\tau(j-1)+m$, $j=1,\dots,J$, where $J=\lfloor \frac{T-m}{\tau}\rfloor$. Then, we can rewrite the sum on the right hand side as

\begin{align*}
\sum_{t=m}^{T}\trace\left(\hat{A}_{t}^{-\frac{1}{2}}\left(\sum_{s=t-m+1}^t Y_{s}^{\top}Y_{s}\right)\hat{A}_{t}^{-\frac{1}{2}}\right)&=\sum_{j=1}^{J}\sum_{t=k_j}^{k_{j+1}-1}\trace\left(\left(\sum_{s=t-m+1}^t Y_{s}^{\top}Y_{s}\right)\cdot \hat{A}_{t}^{-1}\right)\\
& \ \ \ \ \ +\sum_{t=J\tau+m}^T \trace\left(\left(\sum_{s=t-m+1}^t Y_{s}^{\top}Y_{s}\right)\cdot \hat{A}_{t}^{-1}\right)\\
&\le_{(1)}\sum_{j=1}^{J}\sum_{t=k_j}^{k_{j+1}-1}\trace\left(\left(\sum_{s=t-m+1}^t Y_{s}^{\top}Y_{s}\right)\cdot \hat{A}_{t}^{-1}\right)\\
& \ \ \ \ \ +\tau dR_Y^2,
\end{align*}

where $(1)$ follows from that $T-m-J\tau<\tau$ and since $\hat{A}_t\succeq mI$ and $\trace(A)\le d\|A\|_2$ for $A\in\mathrm{R}^{d\times d}$ such that $A\succeq 0$ is symmetric,

\begin{align*}
\trace\left(\left(\sum_{s=t-m+1}^t Y_{s}^{\top}Y_{s}\right)\cdot \hat{A}_{t}^{-1}\right)\le \frac{d}{m}\sum_{s=t-m+1}^t\|Y_s^{\top}Y_s\|_2\le dR_Y^2.
\end{align*}

To bound the first term on the right hand side, since $\hat{A}_t\succeq \hat{A}_{k_j}$ for $t\ge k_j$, we have

\begin{align*}
\sum_{j=1}^{J}\sum_{t=k_j}^{k_{j+1}-1}\trace\left(\left(\sum_{s=t-m+1}^t Y_{s}^{\top}Y_{s}\right)\cdot \hat{A}_{t}^{-1}\right)&\le\frac{4m}{\kappa(G)}\underbrace{\sum_{j=1}^{J}\sum_{t=k_j}^{k_{j+1}-1}\left(\frac{\kappa(G)}{4m}\trace\left(\sum_{s=t-m+1}^t Y_{s}^{\top}Y_{s}\right)\cdot \hat{A}_{k_{j}}^{-1}\right)}_{(a)},
\end{align*}

To bound $(a)$, we further decompose $(a)$ as

\begin{align*}
(a)=\underbrace{\sum_{j=1}^{J}\sum_{t=k_j}^{k_{j+1}-1}\trace\left(\left(-\frac{H_t}{2}+\frac{\kappa(G)}{4m}\sum_{s=t-m+1}^t Y_{s}^{\top}Y_{s}\right)\cdot \hat{A}_{k_{j}}^{-1}\right)}_{(i)}+\underbrace{\frac{1}{2}\sum_{j=1}^{J}\trace\left(\left(\sum_{t=k_j}^{k_{j+1}-1} H_t\right)\cdot \hat{A}_{k_{j}}^{-1}\right)}_{(ii)}.
\end{align*}

To see the bound on the first term, we use Proposition 4.8 from [Simchowitz, 2020]. We include the proof of this result in Section <ref> for completion.

$\forall Y_1,\dots,Y_T$, we have that:

\begin{align*}
\sum_{t=m}^T H_t\succeq \frac{\kappa(G)}{2}\sum_{t=1}^T Y_t^{\top}Y_t-5mR_GR_YI.
\end{align*}

If we let $\tilde{Y}_t=Y_{t+k_j-m}$, and $\tilde{H}_t=H_{t+k_j-m}$, then Lemma <ref> implies that

\begin{align*}
\sum_{t=k_j}^{k_{j+1}-1}\left(\frac{\kappa (G)}{4m}\sum_{s=t-m+1}^t Y_s^{\top}Y_s\right)&\preceq \frac{\kappa(G)}{4}\sum_{t=k_j-m+1}^{k_{j+1}-1}Y_t^{\top}Y_t\\
&\preceq \frac{\kappa(G)}{4}\sum_{t=1}^{\tau+m-1}\tilde{Y}_t^{\top}\tilde{Y_t}\\
&\preceq \sum_{t=m}^{\tau+m-1}\frac{\tilde{H}_t}{2}+\frac{5mR_GR_Y}{2}I\\
\end{align*}

Thus, $(i)$ is bounded by

\begin{align*}
(i)&=\sum_{j=1}^J\underbrace{\left[\left(\sum_{t=k_j}^{k_{j+1}-1}-\frac{H_t}{2}+\frac{\kappa(G)}{4m}\sum_{s=t-m+1}^t Y_{s}^{\top}Y_{s}\right)-\frac{5mR_GR_Y}{2}I\right]}_{\preceq 0}\cdot \hat{A}_{k_{j}}^{-1}+\frac{5mR_GR_Y}{2}\sum_{j=1}^J\trace(\hat{A}_{k_{j}}^{-1})\\
&\le \frac{5dR_GR_Y}{2}\left\lfloor\frac{T}{\tau}\right\rfloor.
\end{align*}

Since by Eq. <ref>, $\hat{A}_{k_{j+1}-1}\preceq \max\{2, \eta\alpha\sigma \tau\} \hat{A}_{k_j}$, $(ii)$ is bounded by

\begin{align*}
(ii)&=\frac{1}{2}\sum_{j=1}^{J}\left(\sum_{t=k_j}^{k_{j+1}-1} H_t\right)\cdot \hat{A}_{k_{j}}^{-1}\\
&=\frac{1}{2\eta \alpha}\sum_{j=1}^{J}\left(\hat{A}_{k_{j+1}-1}-\hat{A}_{k_j-1}\right)\cdot \hat{A}_{k_{j}}^{-1}\\
&\le \frac{\max\{2, \eta\alpha\sigma \tau\}}{2\eta\alpha}\sum_{j=1}^{J}\left(\hat{A}_{k_{j+1}-1}-\hat{A}_{k_j-1}\right)\cdot \hat{A}_{k_{j+1}-1}^{-1}\\
&\le \frac{\max\{2, \eta\alpha\sigma \tau\}}{2\eta\alpha}\sum_{j=1}^{J}\log\left(\frac{|\hat{A}_{k_{j+1}-1}|}{|\hat{A}_{k_{j}-1}|}\right)\\
&\le \frac{\max\{2, \eta\alpha\sigma \tau\}}{2\eta\alpha}\log(|\hat{A}_T|)\\
&\le_{(2)} \frac{\max\{2, \eta\alpha\sigma \tau\}}{2\eta\alpha} d\log(\sigma T),
\end{align*}

where (2) follows from $|\hat{A}_T|\le \|\hat{A}_T\|_2^d$.

Combining, we have

\begin{align*}
(\text{perturbation loss})\le \beta R_G\left[\frac{4m}{\kappa(G)}\left(\frac{5dR_GR_Y}{2}\left\lfloor\frac{T}{\tau}\right\rfloor+ \frac{\max\{2, \eta\alpha\sigma \tau\}}{2\eta\alpha} d\log(\sigma T)\right) + \tau dR_Y^2\right],
\end{align*}

by setting $\tau=\lfloor \sqrt{T}\rfloor$ and assuming $\eta\le \frac{2}{\alpha \sigma \sqrt{T}}\le \frac{2}{\alpha \sigma \tau}$, we have

\begin{align*}
(\text{perturbation loss})\le \beta R_G\left[\frac{10mR_GR_Y}{\kappa(G)}\sqrt{T} + \frac{4md\log(\sigma T) }{\eta\alpha\kappa(G)} +  dR_Y^2\sqrt{T}\right].
\end{align*}

§.§ Bounding movement cost

We prove the following lemma:

The movement cost is bounded by

\begin{align*}
\E\left[\sum_{t=m}^T f_t(x_{t-m+1:t})-\bar{f}_{t}(x_t)\right]\le  \eta dB^*Lm^{2}T.
\end{align*}

The movement cost is bounded by the Lipschitz constant $G$ of $f_t$'s and the Euclidean distances between neighboring iterates.

For any positive definite, symmetric matrix $A$ and its induced norm $\|\cdot\|_{A}$ over $\mathbb{R}^d$, let $C$ be a convex, closed, nonempty subset of $\mathbb{R}^d$, $y\in\mathbb{R}^d$, and $x=\Pi_{C}(y)$ w.r.t. $\|\cdot\|_A$. Then $\forall z\in C$,

\begin{align*}
\|x-z\|_A\le \|y-z\|_A.
\end{align*}

Note that by the above lemma, take $y=x_{t-1}-\eta\hat{A}_{t-m}^{-1}\tilde{g}_{t-m}$, $x=x_t$, $z=x_{t-1}$, and $\|\cdot\|=\|\cdot\|_{\hat{A}_{t-m}}$, we have that $\forall t$,

\begin{align*}
\|x_t-x_{t-1}\|_{\hat{A}_{t-m}}^2&\le \|\eta\hat{A}_{t-m}^{-1}\tilde{g}_{t-m}\|_{\hat{A}_{t-m}}^2=\eta^2 \|\tilde{g}_{t-m}\|_{\hat{A}_{t-m}^{-1}}^2,
\end{align*}

where since $\hat{A}_{t-m}\succeq \hat{A}_{t-m-1}$,

\begin{align*}
\|\tilde{g}_{t-m}\|_{\hat{A}_{t-m}^{-1}}^2&\le d^2 (B^*)^2\sum_{i,j=0}^{m-1}u_{t-i}^{\top} \hat{A}_{t-m-1-i}^{\frac{1}{2}}\hat{A}_{t-m}^{-1}\hat{A}_{t-m-1-j}^{\frac{1}{2}}u_{t-j}\\
&\le d^2(B^*)^2m^2\left\|\hat{A}_{t-m-1}^{\frac{1}{2}}\hat{A}_{t-m}^{-1}\hat{A}_{t-m-1}^{\frac{1}{2}}\right\|_{\mathrm{op}}\\
&\le d^2(B^*)^2m^2,
\end{align*}

\begin{align*}
\|x_t-x_{t-1}\|_2\le \frac{1}{\sqrt{m}}\|x_t-x_{t-1}\|_{\hat{A}_{t-m}}\le \sqrt{m}\eta dB^*.
\end{align*}

By the Lipschitz assumption on $f_t$ over $\K$, the movement cost is bounded by

\begin{align*}
\sum_{t=m}^T \E[f_t(x_{t-m+1:t})-\bar{f}_t(x_t)]&\le L\sum_{t=m}^T \E[\|(x_{t-m+1},\dots, x_t)-(x_t,\dots, x_t)\|_2]\\
&= L \sum_{t=m}^T \E\left[\left(\sum_{s=t-m+1}^{t-1}\|x_s-x_t\|_2^2\right)^{\frac{1}{2}}\right]\\
&\le  L \sum_{t=m}^T \E\left[ \left(\sum_{s=t-m+1}^{t-1}(t-s)\sum_{r=s+1}^{t}\|x_r-x_{r-1}\|_2^2\right)^{\frac{1}{2}}\right]\\
&\le \eta dB^*Lm^{2}T.
\end{align*}

§.§ Bounding underlying regret

The underlying regret can be bounded by the following lemma:

The underlying regret is bounded by

\begin{align*}
\E\left[\sum_{t=m}^T \bar{f}_{t}(x_{t})-\bar{f}_{t}(x)\right]\le \frac{mD^2}{2\eta}+2\eta \sigma \max\{\alpha,1\} d^2(B^*)^2m^3T+\eta \beta \tilde{R}_{G}R_Y^2 d^2 B^* D m^{\frac{9}{2}}T+mB.
\end{align*}

By projection onto convex set, we have that $\forall x\in\K$,

\begin{align*}
\|x_t-x\|_{\hat{A}_{t-m}}^2&\le \|x_{t-1}-x-\eta\hat{A}_{t-m}^{-1}\tilde{g}_{t-m}\|_{\hat{A}_{t-m}}^2\\
&= \|x_{t-1}-x\|_{\hat{A}_{t-m-1}}^2+\frac{1}{2}\|x_{t-1}-x\|_{\eta \alpha H_{t-m}}^2-2\eta \tilde{g}_{t-m}^{\top}(x_{t-1}-x)+\eta^2 \|\tilde{g}_{t-m}\|_{\hat{A}_{t-m}^{-1}}^2\\
&\le \|x_{t-1}-x\|_{\hat{A}_{t-m-1}}^2+\|x_{t-m}-x\|_{\eta\alpha H_{t-m}}^2+\|x_{t-m}-x_{t-1}\|_{\eta\alpha H_{t-m}}^2-2\eta \tilde{g}_{t-m}^{\top}(x_{t-m}-x)\\
& \ \ \ \ \ + 2\eta\tilde{g}_{t-m}^{\top}(x_{t-m}-x_{t-1})+\eta^2\|\tilde{g}_{t-m}\|_{\hat{A}_{t-m}^{-1}}^2,
\end{align*}

where the last inequality follows from that for a square matrix $H\succeq 0$, $\|x+y\|_{H}^2\le 2(\|x\|_{H}^2+\|y\|_{H}^2)$.
Rearranging, we have

\begin{align*}
\tilde{g}_{t-m}^{\top}(x_{t-m}-x)-\frac{1}{2}\|x_{t-m}-x\|_{\alpha H_{t-m}}^2&\le \frac{1}{2\eta}(\|x_{t-1}-x\|_{\hat{A}_{t-m-1}}^2-\|x_t-x\|_{\hat{A}_{t-m}}^2)+\frac{\alpha}{2}\|x_{t-m}-x_{t-1}\|_{H_{t-m}}^2\\
& \ \ \ \ \ +\tilde{g}_{t-m}^{\top}(x_{t-m}-x_{t-1})+\frac{\eta}{2}\|\tilde{g}_{t-m}\|_{\hat{A}_{t-m}^{-1}}^2.
\end{align*}

We can bound the terms on the right hand side as the following: by using the bounds on $\|x_t-x_{t-1}\|_2$ and $\|\tilde{g}_{t}\|_{\hat{A}_{t}^{-1}}$ in Section <ref>, we have

\begin{align*}
\frac{\alpha}{2}\|x_{t-m}-x_{t-1}\|_{H_{t-m}}^2&\le \frac{\alpha\sigma m}{2}\sum_{s=t-m+1}^{t-1}\|x_{s}-x_{s-1}\|_2^2\le \frac{1}{2}\eta^2\alpha\sigma d^2 (B^*)^2 m^3,\\
\tilde{g}_{t-m}^{\top}(x_{t-m}-x_{t-1})&\le \|\tilde{g}_{t-m}\|_{\hat{A}_{t-m}^{-1}}\|x_{t-m}-x_{t-1}\|_{\hat{A}_{t-m}}\\
&\le \|\tilde{g}_{t-m}\|_{\hat{A}_{t-m}^{-1}}\sum_{s=t-m+1}^{t-1}\|x_s-x_{s-1}\|_{\hat{A}_{t-m}}\\
&\le 2\|\tilde{g}_{t-m}\|_{\hat{A}_{t-m}^{-1}}\sum_{s=t-m+1}^{t-1}\|x_s-x_{s-1}\|_{\hat{A}_{s-m}}\\
&\le 2\eta d^2(B^*)^2m^3.
\end{align*}

Therefore, substituting these bounds into the right hand side of the inequality, we have

\begin{align*}
\tilde{g}_{t-m}^{\top}(x_{t-m}-x)-\frac{1}{2}\|x_{t-m}-x\|_{\alpha H_{t-m}}^2&\le \frac{1}{2\eta}(\|x_{t-1}-x\|_{\hat{A}_{t-m-1}}^2-\|x_t-x\|_{\hat{A}_{t-m}}^2)+\frac{1}{2}\eta^2\alpha\sigma d^2 (B^*)^2 m^3\\
& \ \ \ \ \ +2\eta d^2(B^*)^2m^3+\frac{1}{2}\eta d^2(B^*)^2 m^2\\
&\le \frac{1}{2\eta}(\|x_{t-1}-x\|_{\hat{A}_{t-m-1}}^2-\|x_t-x\|_{\hat{A}_{t-m}}^2)\\
& \ \ \ \ \ +2\eta \sigma \max\{\alpha,1\} d^2(B^*)^2m^3.
\end{align*}

Note that since by Lemma <ref>,

\begin{align*}
\E[\tilde{g}_{t-m}\mid \F_{t-2m}]=\sum_{i=1}^m \nabla_i f_{t-m}(x_{t-2m+1:t-m}).
\end{align*}

When bounding perturbation loss, we showed that $\forall t\in[T]$, $\forall i\in[m]$,

\begin{align*}
[\nabla^2 f_t]_{ii}\preceq \beta\tilde{R}_{G}Y_{t-m+i}^{\top}Y_{t-m+i}\preceq \beta\tilde{R}_{G}R_Y^2I_{d\times d}.
\end{align*}

Thus, since $\nabla^2 f_t\succeq 0$, we have

\begin{align*}
\|\nabla^2 f_t\|_2\le \trace(\nabla^2 f_t)=\sum_{i=1}^m \trace([\nabla^2 f_t]_{ii})\le \sum_{i=1}^m d \|[\nabla^2 f_t]_{ii}\|_2\le dm\beta\tilde{R}_{G}R_Y^2.
\end{align*}

By Lemma A.2 in [Gradu et al., 2020], $\forall x$,

\begin{align*}
\nabla \bar{f}_{t}(x)=\sum_{i=0}^{m-1} \nabla_i f_t(x,\dots,x).
\end{align*}

By smoothness of $f_{t-m}$,

\begin{align*}
\|\E[\tilde{g}_{t-m}\mid \F_{t-2m}]-\nabla \bar{f}_{t-m}(x_{t-m})\|_2&\le \sqrt{m}\|\nabla f_{t-m}(x_{t-2m+1:t-m})-\nabla f_{t-m}(x_{t-m},\dots,x_{t-m})\|_2\\
&\le d\beta\tilde{R}_{G}R_Y^2 m^2 \sum_{s=t-2m+1}^{t-m-1}\|x_s-x_{t-m}\|_2\\
&\le d\beta\tilde{R}_{G}R_Y^2 m^2 \sum_{s=t-2m+1}^{t-m-1}\sum_{r=s+1}^{t-m}\|x_s-x_{s-1}\|_2\\
&\le \eta \beta \tilde{R}_{G}R_Y^2 d^2 B^* m^{\frac{9}{2}}.
\end{align*}

\begin{align*}
\E\left[\nabla \bar{f}_{t-m}(x_{t-m})^{\top}(x_{t-m}-x)-\frac{1}{2}\|x_{t-m}-x\|_{\alpha H_{t-m}}^2\right]&\le \frac{1}{2\eta}\E\left[\|x_{t-1}-x\|_{\hat{A}_{t-m-1}}^2-\|x_t-x\|_{\hat{A}_{t-m}}^2\right]\\
& \ \ \ \ \ +\E[(\nabla \bar{f}_{t-m}(x_{t-m})-\tilde{g}_{t-m})^{\top}(x_{t-m}-x)]\\
& \ \ \ \ \ + 2\eta \sigma \max\{\alpha,1\} d^2(B^*)^2m^3\\
&\le \frac{1}{2\eta}\E\left[\|x_{t-1}-x\|_{\hat{A}_{t-m-1}}^2-\|x_t-x\|_{\hat{A}_{t-m}}^2\right]\\
& \ \ \ \ \ +2\eta \sigma \max\{\alpha,1\} d^2(B^*)^2m^3\\
& \ \ \ \ \ +\eta \beta \tilde{R}_{G}R_Y^2 d^2 B^* Dm^{\frac{9}{2}}.
\end{align*}

Since $\nabla^2\bar{f}_t=G_t^{\top}Q_tG_t\succeq \alpha H_t$, summing over all iterations, we have that $\forall x\in\K$,

\begin{align*}
\E\left[\sum_{t=m}^{T}\bar{f}_t(x_t)-\bar{f}_t(x)\right]&\le \sum_{t=2m}^{T} \E\left[\bar{f}_{t-m}(x_{t-m})-\bar{f}_{t-m}(x)\right]+mB\\
&\le \sum_{t=2m}^{T} \E\left[\nabla \bar{f}_{t-m}(x_{t-m})^{\top}(x_{t-m}-x)-\frac{1}{2}\|x_{t-m}-x\|_{\alpha H_{t-m}}^2\right]+mB\\
&\le \frac{1}{2\eta} \sum_{t=2m}^T \E\left[\|x_{t-1}-x\|_{\hat{A}_{t-m-1}}^2-\|x_t-x\|_{\hat{A}_{t-m}}^2\right]+2\eta \sigma \max\{\alpha,1\} d^2(B^*)^2m^3T\\
& \ \ \ \ \ +\eta \beta \tilde{R}_{G}R_Y^2 d^2 B^* m^{\frac{9}{2}}T+mB\\
&\le \frac{1}{2\eta}\E\left[\|x_{2m-1}-x\|_{\hat{A}_{m-1}}^2\right] +2\eta \sigma \max\{\alpha,1\} d^2(B^*)^2m^3T\\
& \ \ \ \ \ +\eta \beta \tilde{R}_{G}R_Y^2 d^2 B^* m^{\frac{9}{2}}T+mB\\
&\le \frac{mD^2}{2\eta}+2\eta \sigma \max\{\alpha,1\} d^2(B^*)^2m^3T+\eta \beta \tilde{R}_{G}R_Y^2 d^2 B^* Dm^{\frac{9}{2}}T+mB.
\end{align*}

§.§ Assembling regret bound

Combining bounds in Section <ref>, Section <ref>, Section <ref> and using that $\sigma\le R_G^2R_Y^2$, the overall expected regret w.r.t. any $x\in\K$ is given by

\begin{align*}
\E[\regret_T(x)]&\le  \beta R_G\left[\frac{10mR_GR_Y}{\kappa(G)}\sqrt{T} + \frac{4md\log(\sigma T) }{\eta\alpha\kappa(G)} +  dR_Y^2\sqrt{T}\right] +  \eta dB^*Lm^{2}T \\
& \ \ \ \ \ +\frac{mD^2}{2\eta}+2\eta \sigma \max\{\alpha,1\} d^2(B^*)^2m^3T+\eta \beta \tilde{R}_{G}R_Y^2 d^2 B^* D m^{\frac{9}{2}}T+mB.
\end{align*}

By taking $\eta=\tilde{\Theta}\left(\frac{1}{\alpha\sqrt{T}}\right)$, we have

\begin{align*}
\E[\regret_T(x)]=\tilde{O}(\sqrt{T}),
\end{align*}

where $\tilde{O}(\cdot)$ hides logarithmic factors in $T$ and all natural parameters $R_G, \tilde{R}_G, R_Y, \kappa(G), B, L, D, \beta, d$.

§.§ Proofs of Technical Lemmas

§.§.§ Proof of Lemma <ref>

Fix a sequence of $Y_1,\dots,Y_T$ and $G$. Let $u$ be any unit vector, and by definition of $H_t$. Denote $u_t=Y_tv$, and let $Y_t=0$, $\forall t\le 0$ and $t>T$. Then,

\begin{align*}
v^{\top}\left(\sum_{t=m}^T H_t\right)v&=\sum_{t=m}^T \left\|\sum_{i=0}^{m-1}G^{[i]}u_{t-i}\right\|_2^2\\
&\ge \sum_{t=1}^{T+m-1}\left\|\sum_{i=0}^{m-1}G^{[i]}u_{t-i}\right\|_2^2-2mR_G^2R_Y^2\\
&\ge_{(1)} \frac{1}{2} \sum_{t=1}^{T+m-1}\left\|\sum_{i=0}^{\infty}G^{[i]}u_{t-i}\right\|_2^2-\sum_{t=1}^{T+m-1}\left\|\sum_{i=m}^{\infty}G^{[i]}u_{t-i}\right\|_2^2-2mR_G^2R_Y^2\\
&\ge_{(2)} \frac{1}{2} \sum_{t=1}^{T+m-1}\left\|\sum_{i=0}^{\infty}G^{[i]}u_{t-i}\right\|_2^2-\frac{R_G^2R_Y^2}{T}-4mR_G^2R_Y^2\\
&=_{(3)}\frac{1}{2} \sum_{t=1}^{\infty}\left\|\sum_{i=0}^{t}G^{[i]}u_{t-i}\right\|_2^2-5mR_G^2R_Y^2\\
&\ge_{(4)} \frac{\kappa(G)}{2}\sum_{t=1}^{T}\|Y_tv\|_2^2-5mR_G^2R_Y^2\\
&=\frac{\kappa(G)}{2}v^{\top}\left(\sum_{t=1}^T Y_t^{\top}Y_t\right)-5mR_G^2R_Y^2.
\end{align*}

where we use the inequality $\|x-y\|_2^2\ge \frac{1}{2}\|x\|_2^2-\|y\|_2^2$ in $(1)$, the decaying assumption on $G$ such that $\sum_{i=m}^{\infty}\|G^{[i]}\|_{\mathrm{op}}\le \frac{R_G}{T}$ in $(2)$, $Y_t=0$ $\forall t\le 0$ and $t>T$ in $(3)$, and definition of $\kappa(G)$ in Assumption <ref> in $(4)$.

§.§.§ Proof of Lemma <ref>

Consider the functions $f_{y}(v)=\|v-y\|_A^2$ on $C$ and $g_{x,z}(t)=f(tz+(1-t)x)$ defined on $t\in[0,1]$. Since $C$ is convex, we have $tz+(1-t)x\in C$, $\forall t\in[0,1]$. By assumption, $x=\Pi_{C}(y)$, $g_{x,z}$ attains minimum at $t=0$. $g_{x,z}'(0)=2(z-x)^{\top}A(x-y)\ge 0$. Then,

\begin{align*}
\|y-z\|_{A}^2=\|y-x+x-z\|_A^2=\|y-x\|_A^2+\|x-z\|_A^2+2(x-y)^{\top}A(z-x)\ge \|x-z\|_A^2.
\end{align*}

§ REGRET OF NBPC (SECTION <REF>)

§.§ Reduction from LQR/LQG control to BQO-AM

Note that by letting $G^{[i]}=\begin{bmatrix}C \\
KC\end{bmatrix}(A+BKC)^{i-1}B\in\mathbb{R}^{(d_{\y}+d_{\uv})\times d_{\uv}}$, we have that the observation-control pair $(\y_t,\uv_t)$ reached by playing DRC matrices $(M_1,\dots, M_{t-1})$ can be expressed as

\begin{align*}
\begin{bmatrix}
\y_t\\
\uv_t
\end{bmatrix}=\begin{bmatrix}
\ynat_t\\
\end{bmatrix}+\sum_{i=1}^t G^{[i]}(\uv_{t-i}-K\y_{t-i})=\begin{bmatrix}
\ynat_t\\
\end{bmatrix}+\sum_{i=1}^t G^{[i]}\left(\sum_{j=0}^{m-1}M_{t-i}^{[j]}\ynat_{t-i-j}\right).
\end{align*}

The sequence of matrices $G=\{G^{[i]}\}_{i\ge 1}$ is called the Markov operator. For simplicity, we assume that the system dynamics and the stabilizing linear policy $K$ is known in this section. With these knowledge, the above equation implies that the signals $\y_t^K$ can be directly computed by the learner from the observations.

Moreover, let $d=md_{\y}d_{\uv}$, and let $\embed:(\mathbb{R}^{d_{\uv}\times d_{\y}})^{m}\rightarrow\mathbb{R}^d$ denote the natural embedding of a DRC controller $M$ in $\mathbb{R}^d$, with inverse $\embed^{-1}$, i.e. for $M^{[0]},\dots,M^{[m-1]}\in\mathbb{R}^{d_{\uv}\times d_{\y}}$, $ k \in [m-1]$, $i\in [d_{\uv}]$, $j\in [d_{\y}]$,

\begin{align*}
\embed(M^{[0]},\dots, M^{[m-1]})_{kd_{\uv}d_{\y}+(i-1)d_{\y}+j}=M^{[k]}_{ij}.
\end{align*}

Denote $\embed_{\y}:(\mathbb{R}^{d_{\y}})^{m}\rightarrow \mathbb{R}^{d_{\uv}\times d}$ such that $\forall M^{[0]},\dots,M^{[m-1]}\in\mathbb{R}^{d_{\uv}\times d_{\y}}$,

\begin{align*}
\embed_{\y}(\ynat_{t-m+1},\dots,\ynat_{t})\embed(M^{[0]},\dots,M^{[m-1]})=\sum_{j=0}^{m-1}M^{[j]}\ynat_{t-j}.
\end{align*}

We shorthand $Y_t=\embed_{\y}(\ynat_{t-m+1},\dots,\ynat_{t})$, and $\embed(M)=\embed(M^{[0]},\dots,M^{[m-1]})$. An explicit formulation of $\embed_{\y}$ is given by

\begin{align*}
Y_{i,j+1:j+d_{\y}}=\ynat_{t-k+1} \ \ \ \text{if } \ \ \ j=(k-1)d_{\uv}d_{\y}+(i-1)d_{\y}, \ \ \ \forall i\in[d_{\uv}], k\in[m].
\end{align*}

Therefore, for any controller that plays DRC policies, the cost function can be re-written as

\begin{align*}
Q_t & \mathbf{0}_{d_{\y}\times d_{\uv}}\\
\mathbf{0}_{d_{\uv\times d_{\y}}} & R_t
\end{bmatrix}\left(B_t+\sum_{i=0}^{m-1}G^{[i]}Y_{t-i}\embed(M_{t-i})\right)\\
\end{align*}

where $B_t=(\ynat_t,K\ynat_t)+\sum_{i=m}^t G^{[i]}Y_{t-i}\embed(M_{t-i})$. Let $\bar{f}_t$ denote its induced unary form, i.e. $\bar{f}_t(\embed(M))=f_t(\embed(M),\dots,\embed(M))$. Note that $f_t$ is an adaptive function of the learners decision before the time $t-m+1$ through $B_t$. $B_t$ is independent of the algorithm's decisions $M_{t-m+1:t}$, and $Y_t$'s are independent of the algorithm's decisions. Therefore, the adversarial model in Assumption <ref> is satisfied.

§.§ Regularity conditions

$\forall M_1,\dots, M_T\in\M(m,R_{\M})$,

* For $m\ge 1+\left(\log\frac{1}{1-\gamma}\right)^{-1}\log T$,

\begin{align*}
&\sum_{i=0}^{\infty} \|G^{[i]}\|_{\mathrm{op}}\le 1+\frac{c\kappa\sqrt{1+\kappa^2}\kappa_C\kappa_B}{\gamma}=: R_G, \ \ \ \sum_{i=m}^{\infty} \|G^{[i]}\|_{\mathrm{op}}\le \frac{R_G}{T},  \\
&\sum_{i=1}^{\infty} \|C(A+BKC)^{i-1}B\|_{\mathrm{op}}\le \frac{c\kappa_C\kappa_B\kappa}{\gamma}=: R_{G_{\y}}, \ \ \ \sum_{i=1}^{\infty} \|C(A+BKC)^{i-1}\|_{\mathrm{op}}\le \frac{c\kappa_C\kappa}{\gamma}=: R_{G_{\y},K},\\
&\max_{1\le i\le m-1}\|(G^{[i]})^{\top}G^{[i]}\|_2\le(1+\kappa^2)\kappa_C^2\kappa_B^2\kappa^2 =: \tilde{R}_G.
\end{align*}

* $\max_{t\in[T]}\|\ynat_t\|_2\le (R_{G,K}+1)R_{\w,\e}=:R_{\mathrm{nat}}$.

* $\max_{t\in[T]}|c_t(\y_t^{M_{1:t-1}}, \uv_{t}^{M_{1:t}})|=\max_{t\in[T]}|f_t(\embed(M_{t-m+1}),\dots,\embed(M_t))|\le \beta R_{\mathrm{nat}}^2((1+R_{G_{\y}}R_{\M})^2(1+2\kappa^2)+2R_{\M}^2)=:B$.

* $\max_{M^1,M^2\in\M(m,R_{\M})}\|\embed(M^1)-\embed(M^2)\|_2\le \sqrt{m\max\{d_{\uv},d_{\y}\}} R_{\M}=:D$.

* $\max_{t\in[T]}\|Y_t\|_2\le \sqrt{md_{\y}d_{\uv}^2}R_{\mathrm{nat}}=:R_Y$.

* $\max_{t\in[T]}\|\nabla f_t(\embed(M_{t-m+1}),\dots,\embed(M_t))\|\le 2\beta \sqrt{m} R_YR_G (R_YR_GD+2R_{\mathrm{nat}})=:L$.

* $\kappa (G)\ge \frac{1}{4}\min\{1,\kappa^{-2}\}$.

By Assumption <ref>, we know that

\begin{align*}
\sum_{i=0}^{\infty}\|G^{[i]}\|_{\mathrm{op}}&\le 1+\sum_{i=1}^{\infty}\sqrt{\|C(A+BKC)^{i-1}B\|_{\mathrm{op}}^2+\|KC(A+BKC)^{i-1}B\|_{\mathrm{op}}^2}\\
&\le 1+c\sqrt{1+\kappa^2}\kappa_C\kappa_B\sum_{i=1}^{\infty}\|HL^{i-1}H^{-1}\|_{2}\\
&\le 1+c\kappa\sqrt{1+\kappa^2}\kappa_C\kappa_B \sum_{i=0}^{\infty} (1-\gamma)^i\\
\end{align*}

where $c$ is some constant possibly depending on the dimension of $H,L$. By similar argument and the choice of $m$, we can establish the other inequalities. Moreover,

\begin{align*}
\max_{1\le i\le m-1}\|(G^{[i]})^{\top}G^{[i]}\|_2\le (1+\kappa^2)\kappa_C^2\kappa_B^2\kappa^2(1-\gamma)^{2(i-i)}\le(1+\kappa^2)\kappa_C^2\kappa_B^2\kappa^2=\tilde{R}_G.
\end{align*}

Therefore, denote $\xnat_t$ as the would-be state if the linear policy $K$ was played from the beginning of the time, we have

\begin{align*}
\max_{t\in[T]}\|\ynat_t\|_2=\max_{t\in[T]}\left\|C\xnat_t+\e_t\right\|=\max_{t\in[T]}\left\|C\sum_{i=0}^{t-1}(A+BKC)^{i}\w_{t-i}+\e_t\right\|_2\le (R_{G,K}+1)R_{\w,\e},
\end{align*}

\begin{align*}
\max_{t\in[T]}\left\|\sum_{j=0}^{m-1}M_t^{[j]}\ynat_{t-j}\right\|_2\le \max_{t\in[T]} \|M_t\|_{\ell_1,\mathrm{op}}\max_{t\in[T]}\|\ynat_t\|_2\le R_{\M}R_{\mathrm{nat}},
\end{align*}

which implies that $\max_{t\in[T]}\left\|\y_t^{M_{1:t-1}}\right\|\le R_{\mathrm{nat}}(1+R_{G_{\y}}R_{\M})$. Thus, $c_t$'s are bounded by

\begin{align*}
\max_{t\in[T]} c_t(\y_t^{M_{1:t-1}},\uv_t^{M_{1:t}})&\le \beta\left(\|\y_t^{M_{1:t-1}}\|_2^2+\left\|K\y_t^{M_{1:t-1}}+\sum_{j=0}^{m-1}M_t^{[j]}\ynat_{t-j}\right\|_2^2\right)\\
&\le \beta R_{\mathrm{nat}}^2((1+R_{G_{\y}}R_{\M})^2(1+2\kappa^2)+2R_{\M}^2)\\
\end{align*}

The diameter of $\M(m,R_{\M})$ is given by

\begin{align*}
\max_{M_1,M_2\in\M(m,R_{\M})}\|\embed(M_1)-\embed(M_2)\|_2&\le \sqrt{m} \max_{M_1,M_2\in\M(m,R_{\M})}\max_{0\le j\le m-1}\|M_1^{[j]}-M_2^{[j]}\|_F\\
&\le \sqrt{m\max\{d_{\uv},d_{\y}\}}\max_{M_1,M_2\in\M(m,R_{\M})}\max_{0\le j\le m-1}\|M_1^{[j]}-M_2^{[j]}\|_{\mathrm{op}}\\
&\le \sqrt{m\max\{d_{\uv},d_{\y}\}} R_{\M},
\end{align*}

where the second inequality follows from that $\|A\|_F\le \sqrt{\mathrm{rank}(A)}\sigma_{\max}(A)\le \sqrt{\mathrm{rank}(A)}\|A\|_{\mathrm{op}}$.

To bound the gradient of $f_t$, denote $\nabla_i f_t$ as the gradient of $f_t$ w.r.t. $\embed(M_{t-m+i})$, and then we have $\forall t\in[T], i\in[m]$,

\begin{align*}
\left\|\nabla_i f_t(\embed(M_{t-m+1}),\dots,\embed(M_t))\right\|_2&\le 2\beta\left\|Y_{t-m+i}^{\top} (G^{[m-i]})^{\top}\left(B_t+\sum_{i=0}^{m-1}G^{[i]}Y_{t-i}\embed(M_{t-i})\right)\right\|_2 \\
&\le 2\beta \max_{t\in[T]}\|Y_t\|_{\mathrm{op}} R_G\left(\max_{t\in[T]}\|B_t\|_2+R_G\max_{t\in[T]}\|Y_t\|_{\mathrm{op}}D\right)
\end{align*}

We can bound $B_t$ and $Y_t$ as follows:

\begin{align*}
&\max_{t\in[T]}\|B_t\|_2=\max_{t\in[T]}\left\|\ynat_t+\sum_{i=m}^t G^{[i]}\left(\sum_{j=0}^{m-1}M_{t-i}^{[j]}\ynat_{t-j}\right)\right\|_2\le R_{\mathrm{nat}}\left(1+\frac{R_GR_{\M}}{T}\right),\\
&\max_{t\in[T]}\|Y_t\|_2\le \sqrt{md_{\y}d_{\uv}^2}\max_{t\in[T]}\|\y_t^{K}\|_2\le \sqrt{md_{\y}d_{\uv}^2}R_{\mathrm{nat}}=:R_Y,
\end{align*}

where the second inequality is given by the definition of $\embed_{\y}$. Thus, assuming $\frac{R_GR_{\M}}{T}\le 1$,

\begin{align*}
\max_{t\in[T]}\|\nabla f_t(\embed(M_{t-m+1}),\dots,\embed(M_t))\|_2&\le \sqrt{m} \max_{t\in[T], 1\le i\le m}\|\nabla_i f_t(\embed(M_{t-m+1}),\dots,\embed(M_t))\|_2\\
&\le 2\beta \sqrt{m} R_YR_G (R_YR_GD+2R_{\mathrm{nat}})\\
\end{align*}

The last inequality on $\kappa(G)\ge \frac{1}{4}\min\{1,\kappa^{-2}\}$ is given by Lemma 3.1 in [Simchowitz, 2020].

§.§ : Newton Bandit Perturbation Controller Algorithm

Newton Bandit Perturbation Controller ()

Input: DRC policy class $\M(m,R_{\M})$, step size $\eta>0$, time horizon $T$, system Markov operator $G$, $(\kappa,\gamma)$-strongly stable linear policy $K$, strong convexity parameter $\alpha>0$.

[1]
Initialize: $M_{1}^{[j]}=\dots=M_{m}^{[j]}=\mathbf{0}_{d_{\uv}\times d_{\y}}$, $\forall j\in[m]$, $\tilde{g}_{0:m-1} = \mathbf{0}_{md_{\uv}d_{\y}}$, $ \hat{A}_{0:m-1} = mI_{md_{\uv}d_{\y}\times md_{\uv}d_{\y}}$.
Sample $\eps_t\sim S^{md_{\uv}d_{\y}-1}$ i.i.d. uniformly at random for $t=1,\dots,m$.
Set $\widetilde{M}_t = \embed^{-1}(\embed(M_t) + \hat{A}_{t-1}^{-\frac{1}{2}}\eps_t)$, $t=1,\dots,m$.
Play control
Play control $\uv_t=K\y_t$, incur cost $c_t(\y_t,\uv_t)$ for $t=1,\dots, m$.
$t = m, \ldots, T$

Play control $\uv_t=\uv_t^{\widetilde{M}_t}=K\y_t+\sum_{j=0}^{m-1}\widetilde{M}_t^{[j]}\y_{t-j}^K$, incur cost $c_t(\y_t,\uv_t)=f_t(\embed(\widetilde{M}_{t-m+1:t}))$.
System involves as $\x_{t+1}=A\x_t+B\uv_t+\w_t$ and $\y_{t+1}=C\x_{t+1}+\e_{t+1}$. Receive new observation $\y_{t+1}$, compute signal
$$\ynat_{t+1}=\y_{t+1}-\sum_{i=1}^{t+1} G^{[i]}\left(\sum_{j=0}^{m-1}\widetilde{M}_{t+1-i}^{[j]}\ynat_{t+1-i-j}\right),$$

where $\forall t\le 0$, $\ynat_t\defeq 0$ and $\widetilde{M}_t\defeq 0$.
Compute Hessian information matrix $H_t\in\mathbb{R}^{md_{\y}d_{\uv}\times md_{\y}d_{\uv}}$:

\begin{align*}
H_t=G_t^{\top}G_t, \ \ \ G_t=\sum_{i=0}^{m-1}G^{[i]}Y_{t-i}, \ \ \ Y_t=\embed_{\y}(\ynat_{t-m+1},\dots,\ynat_t).
\end{align*}

Update $\hat{A}_t=\hat{A}_{t-1}+\frac{\eta\alpha}{2}H_t$.
Create gradient estimate: $\tilde{g}_{t}=md_{\uv}d_{\y}c_t(\y_t,\uv_t) \sum_{j=0}^{m-1}\hat{A}_{t-1-j}^{\frac{1}{2}}\eps_{t-j}$.
$ M_{t+1} = \embed^{-1}\left(\prod_{\embed(\M(m,R_{\M})}^{\hat{A}_{t-m+1}} \left[ \embed(M_t) - \eta \hat{A}_{t-m+1}^{-1}  \tilde{g}_{t-m+1}  \right]\right)$.
Sample $\eps_{t+1}\sim S^{md_{\uv}d_{\y}-1}$ uniformly at random, independent of previous steps.
Set $\widetilde{M}_{t+1}=\embed^{-1}(\embed(M_{t+1})+\hat{A}_{t-m+1}^{-\frac{1}{2}}\eps_{t+1})$.

§.§ Proof of Theorem <ref>

Let $R_G, R_Y, B, D, L$ be consistent with the notations in Lemma <ref>, and

$$M^*=\argmin_{M\in\M(m,R_{\M})}\sum_{t=1}^T c_t(\y_t^M,\uv_t^M).$$

Note that treating the first $2m-2$ steps as burn-in loss, we have

\begin{align*}
\regret_T(\texttt{NBPC})&\le 2mB+\left(\sum_{t=2m-1}^Tf_t(\embed(\widetilde{M}_{t-m+1:t}))-\bar{f}_t(\embed(M^*))\right)\\
& \ \ \ \ \ +\left(\sum_{t=2m-1}^T\bar{f}_t(\embed(M^*))-c_t(\y_t^{M^*},\uv_t^{M^*})\right).
\end{align*}

By Theorem <ref> and Lemma <ref>, by taking $\eta=\tilde{\Theta}\left(\frac{1}{\alpha\sqrt{T}}\right)$, the second term is bounded by $\tilde{O}(\sqrt{T})$, where $\tilde{O}$ hides logarithmic terms in $T$ and natural parameters as those derived in Lemma <ref>. The third term can be bounded as the following:

\begin{align}
\label{eq:comparator-loss-known}
\sum_{t=2m-1}^T\bar{f}_t(\embed(M^*))-c_t(\y_t^{M^*},\uv_t^{M^*})
\le L\sum_{t=2m-1}^T \left\|\sum_{i=m}^t G^{[i]}Y_{t-i}(\embed(M^*)-\embed(M_{t-i}))\right\|_2\le L R_GR_YD.
\end{align}

§ EXTENSION TO CONTROL OF UNKNOWN SYSTEMS (SECTION <REF>)

Consider the setting the dynamics of the system are unknown to the learner. In this case, the learner needs to first estimate the system dynamics and obtain an estimated Markov operator $\hat{G}$, and then use $\hat{G}$ in place of $G$ in the control algorithm.

This section will be organized as the following: Section <ref> will analyze the regret guarantee if instead of the true Markov operator $G$, the learner receives an estimate $\hat{G}$ satisfying $\|\hat{G}-G\|_{\ell_1,\mathrm{op}}\le \eps_G$.

§.§ Known Stabilizing Controller

First, we consider the case where a $(\kappa, \gamma)$-stabilizing linear policy $K$ is known to the learner. [Simchowitz, 2020] has studied this problem in the full information setting, where they proved a quadratic sensitivity of the control regret to the estimation error $\eps_G$ of $\hat{G}$. The main difference between our setting and and that of [Simchowitz, 2020] comes from the bandit gradient estimation step and the delayed updates in Algorithm <ref> to establish conditional independence.

We start with the assumption that there exists an estimation algorithm that returns a $\hat{G}$ sufficiently close to the true Markov operator $G$:

Assume that the learner has access to an estimate $\hat{G}$ of the Markov operator $G$ satisfying

\begin{align*}
\|G-\hat{G}\|_{\ell_1,\mathrm{op}}\le \eps_G, \ \ \ \hat{G}^{[i]}=\mathbf{0}_{(d_{\y}+d_{\uv})\times d_{\uv}}, \forall i\ge m.
\end{align*}

The system estimation via least-square algorithm used in [Simchowitz et al., 2020, Simchowitz, 2020, Sun et al., 2023] satisfies the conditions in Assumption <ref> after $N=O(1/\eps_G^2)$ iterations with high probability (see, for instance, Theorem 6b in [Simchowitz et al., 2020]). Since we pay at most $BN$-regret during the estimation step, $\tilde{O}(\sqrt{T})$ is preserved if $\eps_G$ propagates quadratically in the regret bound (i.e. the learner's regret suffers an additional $\tilde{O}(T\eps_G^2)$ due to estimation error).

Preliminaries. During the course of the algorithm, the learner uses the Markov operator to compute $\hat{\y}_t^K$. Therefore, with an estimated Markov operator, the $\y_t^K$'s computed by the learner are no longer accurate. When reducing to BQO-AM, the loss functions that the learner sees become

\begin{align*}
\hat{F}_t(\embed(M_{t-m+1:t}))=\left(\hat{B}_t+\sum_{i=0}^{m-1}\hat{G}^{[i]}\hat{Y}_{t-i}\embed(M_{t-i})\right)^{\top}\begin{bmatrix}
Q_t & \mathbf{0}_{d_{\y}\times d_{\uv}} \\
\mathbf{0}_{d_{\uv}\times d_{\y}} & R_t
\end{bmatrix}
\left(\hat{B}_t+\sum_{i=0}^{m-1}\hat{G}^{[i]}\hat{Y}_{t-i}\embed(M_{t-i})\right),
\end{align*}

where $\hat{B}_t=(\hat{\y}_t^K, K\hat{\y}_t^K), \hat{Y}_t$ are the counterparts of $B_t, Y_t$ defined in Section <ref> using estimates $\hat{G}$ and $\hat{\y}_t^K$. Note that we do not have the additional terms in $\hat{B}_t$ that depends on the learner's past controls since $\hat{G}^{[i]}=\mathbf{0}_{(d_{\y}+d_{\uv})\times d_{\uv}}$ for $i\ge m$. First, we consider a pseudo-loss function:

\begin{align*}
\tilde F_t(\embed(M_{t-m+1:t}))=\left(\tilde{B}_t+\sum_{i=0}^{m-1}G^{[i]}\hat{Y}_{t-i}\embed(M_{t-i})\right)^{\top}\begin{bmatrix}
Q_t & \mathbf{0}_{d_{\y}\times d_{\uv}} \\
\mathbf{0}_{d_{\uv}\times d_{\y}} & R_t
\end{bmatrix}
\left(\tilde{B}_t+\sum_{i=0}^{m-1}G^{[i]}\hat{Y}_{t-i}\embed(M_{t-i})\right),
\end{align*}

where $\tilde{B}_t=(\y_t^K, K\y_t^K)$.
Let $\hat{f}_t,\tilde{f}_t$ denote their induced unary form, respectively. Although the learner has no access to $\tilde{F}_t$ , Proposition D.8 in [Simchowitz, 2020] suggests that the control regret for unknown system is implied by the bound for some $\nu>0$ on the following quantity:

\begin{align}
\label{eqn:reduced-control-regret}
\E\left[\sum_{t=m}^T\tilde{F}_t(\embed(\widetilde{M}_{t-m+1:t}))-\tilde{f}_t(\embed(M))+\nu\sum_{t=m}^T\|Y_t(\embed(M_{t-m+1})-\embed(M))\|_2^2\right],
\end{align}

where $\widetilde{M}_t$ is the DRC policy played by the learner at time $t$, and $M_t$ is the projected DRC policy by Algorithm <ref> at time $t$.
Therefore, in the rest of this section, we focus on bounding the quantity in Eq. <ref>.

§.§ High-level proof

Throughout this section, we assume that Assumption <ref> holds. For a comparator $x\in\embed(\M(m,R_{\M}))$, we denote

\begin{align*}
\widetilde{\regret}_T(x)=\sum_{t=m}^T \tilde{F}_t(y_{t-m+1:t})-\tilde{f}_t(x), \ \ \ \widehat{\regret}_T(x)=\sum_{t=m}^T \hat{F}_t(y_{t-m+1:t})-\hat{f}_t(x),
\end{align*}

where $y_t=\embed(\widetilde{M}_t)$. Similarly, we denote $x_t=\embed(M_t)$. Suppose Algorithm <ref> is run with $\hat{F}_t$ with a slightly modified cumulative Hessian $\hat{A}_t=mI+\frac{\eta\alpha}{6}\sum_{s=m}^t\hat{H}_s$, where $\hat{H}_t=\hat{G}_t^{\top}\hat{G}_t$, $\hat{G}_t=\sum_{i=0}^{m-1}\hat{G}^{[i]}\hat{Y}_{t-i}$. We start by noting that $\widehat{\regret}_T(x)$ can be bounded via the regret bound for known systems by treating $\hat{G}$ as the true Markov operator.

$\forall x\in\embed(\M(m,R_{\M}))$, $\E\left[\widehat{\regret}_T(x)\right]\le \tilde{O}(\sqrt{T})$.

Lemma <ref> and Lemma <ref> relates the regret of controlling an unknown system to $\widehat{\regret}_T(x)$.

$\forall \nu>0$, $\exists x^*\in\embed(\M(\frac{m}{3}, \frac{R_{\M}}{2}))$ such that

\begin{align*}
\E\left[\mathrm{ControlRegret}_T\right]\le \E[\widetilde{\regret}_T(x^*)]+\tilde{O}(1)\cdot T\eps_G^2\left(1+\frac{1}{\nu}\right)+\nu\sum_{t=m}^T \E[\|\hat{Y}_t(x_t-x^*)\|_2^2]+\tilde{O}(1),
\end{align*}

where $\mathrm{ControlRegret}_T:=\sum_{t=1}^T c_t(\y_t,\uv_t)-\min_{M\in\M(\frac{m}{3},\frac{R_{\M}}{2})}\sum_{t=1}^T c_t(\y_t^M, \uv_t^M)$.

Lemma <ref> is an analogous result to Lemma 5.1-5.4 in [Simchowitz, 2020], providing a relationship between the two quantities defined above.

$\forall \nu>0$, the regret for any $x\in\embed(\M(m,R_{\M}))$ for $\tilde{F}_t$ is bounded by

\begin{align*}
\E[\widetilde{\regret}_T(x)]&\le 2B(\E[\widehat{\regret}_T(x)])+\frac{\nu}{m}\sum_{t=m}^T\sum_{i=0}^{m-1}\E\left[ \|\hat{Y}_{t-i}(x_{t}-x)\|_2^2\right]-\frac{\alpha}{12}\sum_{t=m}^T \E\left[\|x_t-x\|_{\tilde{H}_t}^2\right]\\
& \ \ \ \ \ + \left(\beta R_{\hat{Y}}^2+\frac{\alpha R_{\hat{Y}}^2D^2}{3}+\frac{12}{\alpha}\beta^2D^2+\frac{(\beta DR_G)^2m}{\nu}\right)\eps_G^2T,
\end{align*}

where $B(\cdot)$ denotes any upper bound on a given quantity, and $\tilde{H}_t$ is defined analogously to $\hat{H}_t$ for $\tilde{F}_t$'s.

For $\nu=\frac{\alpha \kappa(G)}{192}$, we have

\begin{align*}
\frac{2\nu}{m}\sum_{t=m}^T\sum_{i=0}^{m-1}\E\left[ \|\hat{Y}_{t-i}(x_{t}-x)\|_2^2\right]-\frac{\alpha}{12}\sum_{t=m}^T \E\left[\|x_t-x\|_{\tilde{H}_t}^2\right]\le \tilde{O}(\sqrt{T}),
\end{align*}

and therefore by Lemma <ref>,

\begin{align*}
\E[\widetilde{\regret}_T(x)]&\le 2B(\E[\widehat{\regret}_T(x)])-\frac{\alpha\kappa(G)}{192m}\sum_{t=m}^T\sum_{i=0}^{m-1}\E\left[ \|\hat{Y}_{t-i}(x_{t}-x)\|_2^2\right]+\tilde{O}(1)\cdot \eps_G^2T.
\end{align*}

Combining Lemma <ref>-<ref>, we conclude that