
\section{Introduction}
    
    Markov Decision Processes are a ubiquitous model for decision making that captures a wide array of applications including autonomous road navigation, robotics, gaming and many more. In the finite-horizon version of the model, the goal of the agent is to minimize her expected total loss over a fixed number of time steps. Classic results in finite-horizon MDPs state that the optimal policy of the agent is deterministic; namely, a mapping between each state and time step to an action for the agent to play.

    In this paper, we study the problem of \emph{Online MDPs with Aggregate Feedback} which is played for $K$ episodes. The dynamics of the MDP are fixed but unknown to the learner. After each episode, in addition to observing her trajectory within the MDP, the agent also gets to view her total loss along this trajectory. The agent, however, does not get to observe the individual losses of specific states and actions that comprise the trajectory.
    This setting was recently considered in \cite{efroni2020reinforcement} where the authors derived computationally-efficient learning algorithms for the case where the losses are sampled i.i.d.\ from some unknown distribution.
    In this work, we assume that the losses are non-stochastic and may be chosen by an adversary---a significantly more challenging task.
    
    The adversarial setting is a variant of online MDPs~\citep{even2009online} with initially unknown model dynamics, previously considered either when full information about the losses is received~\citep{neu2010online}, or with traditional bandit feedback where the agent sees the individual losses of all states and actions that were visited along each of her generated trajectories~\citep{rosenberg2019online}. 
    Commonly, the main solution technique is to separate the $K$ episodes into $O(\log K)$ epochs; in each epoch, the agent runs a no-regret algorithm using an estimate of the dynamics obtained from observations accrued up to the beginning of the epoch. 
    %
    To tackle bandit feedback in general, it is common practice to employ a full-information learning algorithm which is fed with an unbiased estimate of the losses in each episode.
    Nevertheless, in our setup we do not know the MDP dynamics, so it is hopeless for the learner to generate such an unbiased estimate since it is impossible to calculate the probability of visiting each state and action without exact knowledge of the transition distributions.
    This impediment was overcome in \cite{jin2020learning} that followed the ``optimism in the face of uncertainty'' principle: they fed the learning algorithm with a certain underestimate of the loss. 
    This drives the agent to explore under-sampled state-action pairs, helps to obtain better estimates of the dynamics, and reduces the overall bias of the loss estimators over time.
    
    We utilize a similar approach to tackle the aggregate feedback by reducing the problem to $O(\log K)$ epochs in each of which we solve a variant of linear bandits over our current estimate of the model dynamics. We name the learning problem in each epoch  \emph{Distorted Linear Bandits\xspace} (DLB\xspace). This is a variant of the linear bandits problem in which, after choosing an action, it can be distorted (i.e., perturbed) in an adversarial manner before it is played. This distortion unavoidably introduces a non-negligible bias when trying to generate an estimate of the loss vector.
    %
    The DLB\xspace problem is also interesting in its own right, capturing scenarios where there is uncertainty regarding the action that is actually taken, which might deviate significantly from the action intended to be taken---a phenomenon that occurs in applications in robotics and control, where the actions are continuous in~nature.
    
    We derive two learning algorithms for the DLB\xspace setting that yield a $O(\sqrt{K})$ regret bound, yet mitigate the estimation bias in different ways.
    %
    Our first algorithm, based on EXP2 \citep{awerbuch2004adaptive, mcmahan2004online}, utilizes an optimistic approach by feeding the algorithm with underestimates of the loss.
    This technique, it turns out, is not computationally efficient due to the non-convex nature of these underestimates.
    %
    Our second algorithm, however, runs in polynomial-time per episode.
    It is a variant of Online Mirror Descent that uses a self-concordant barrier function as a regularizer \citep{abernethy2009competing} with a series of increasing learning rates.
    The idea of using increasing learning rates to alleviate estimation bias is used in various recent works \citep{bubeck2017kernel, agarwal2017corralling, lee2020bias}.
    Intuitively, it gives the learner a ``boost'' towards playing better actions whenever the estimation bias is large.
    
    \subsection{Summary of Contributions}
    
        The main contributions of the paper are as follows:
        %
        \begin{itemize
            \item We introduce the setting of Online MDPs with Aggregate Bandit Feedback, where the dynamics are initially unknown and costs may be chosen by an adversary; to the best of our knowledge, such a problem has not been studied before.
            \item We establish an efficient reduction from Online MDPs with Aggregate Bandit Feedback to the novel {Distorted Linear Bandits\xspace} (DLB\xspace) problem.
            \item We give a computationally-efficient online learning algorithm for the DLB\xspace problem with $O(\sqrt{T})$ regret over $T$ rounds.
            \item Combining the two techniques, we obtain a computationally-efficient online learning method for Online MDPs with Aggregate Bandit Feedback with $O(\sqrt{K})$ regret over $K$ episodes.
        \end{itemize}
    
        In \cref{sec:reduction-main} we present the Online MDP with Aggregate Feedback model explicitly and give our main result. We also present the Distorted Linear Bandits\xspace (DLB\xspace) setting, the reduction between the two models, and prove our regret bound for online MDPs. In \cref{sec:blb-algorithms} we give our two algorithms for the DLB\xspace setting and analyze their regrets.
    
    
    \subsection{Additional Related Work}
    
        The study of regret minimization in reinforcement learning dates back to \cite{jaksch2010near}
       
        who considered an MDP with unknown dynamics and losses, but where the losses are sampled i.i.d. This model was further studied in \cite{azar2017minimax,zanette2019tighter} that provided improved~bounds.
       
        
        Online MDPs were introduced in
        \cite{even2009online} who studied MDPs with known dynamics and adversarially changing losses. Later \cite{neu2013online} extended the online MDP to handle bandit feedback.
        \cite{abbasi2013online} considered MDPs where both the dynamics and the losses change adversarially. Their algorithm, however, is not computationally-efficient as they show in a hardness result. All the above results assume access to individual losses while in this work we assume the learner observes only the aggregate loss of an episode.

        Bandit linear optimization has been extensively studied under both semi-bandit and bandit feedback; for an extensive survey of this literature, see \citet{SlivkinsBook,CsabaTorBook}. 
        %
       
        %
        Misspecified linear bandits were introduced in \cite{GhoshCG2017} where the loss of each action can be perturbed arbitrarily. They give an impossibility result for large sparse deviations and a regret bound for small deviations (see also \citealp{LattimoreSW2020}).
        %
        Our model differs from misspecified linear bandit, most importantly, in that we allow for adversarial losses. In addition, we also differ both in the fact that the deviations might be large (and we can only globally bound them) and the fact that the loss is linear but with respect to a distorted action.

\section{Preliminaries} \label{sec:prelims}

    \paragraph{Finite-Horizon MDPs.}
    
    A finite-horizon Markov Decision Process is a tuple $(S,A,s_1,P,\ell,H)$ defined as follows. $S$ is a finite set of states; $A$ is a finite set of actions; $s_1\in S$ is the start state; the integer $H$ defines the horizon.
    The transition function $P$ defines a probability distribution $P(s' \mid s,a,h)$ of the next state $s'$ given the current state $s$, action $a$, and time $h\in[H]$. The loss function is $\ell$ defines a loss $\ell(h, s,a,s') \in [0,1]$ for every time $h\in[H]$ state $s$, action $a$, and next state $s'$.
    
    A (randomized) policy $\pi : S \times [H] \mapsto \Delta(A)$ maps each state and time to a probability distribution over the actions.
    A trajectory is a sequence  $(s_1, a_1, \ldots, s_H, a_{H}, s_{H+1})$.
    The probability of such trajectory with respect to a policy $\pi$ and a transition function $P$ is $\prod_{h=1}^H \pi(a_h \mid s_h,h) P(s_{h+1} \mid s_h,a_h,h)$.
    The accumulated loss of such a trajectory using a loss function $\ell$ is $\sum_{h=1}^{H} \ell(h, s_h,a_h,s_{h+1})$. The expected loss of a policy $\pi$ with respect to a transition function $P$ and loss function $\ell$ is 
    \begin{align*}
        L^{\pi,P,\ell}
        = 
        \mathbb{E} \brk[s]4{
        \sum_{h=1}^{H}\ell(h, s_h,a_h,s_{h+1})}
        =
        \sum_{\substack{(h,s,a,s') \in \\ [H] \times S \times A \times S}} \ell(h, s,a,s') ~ \Pr[s_h=s,a_h=a,s_{h+1}=s']
        .
    \end{align*}
    
    \paragraph{Occupancy Measures.}
        
        A combination of a policy $\pi$ and a transition function $P$ provide an occupancy measure $x^{\pi, P}$ such that $x^{\pi, P}(h,s,a,s')$ is the probability, according to $P$ and $\pi$, of being at state $s$ at time $h$, playing action $a$, and transitioning to state $s'$. 
        Formally,
        \[
            x^{\pi,P}(h, s,a,s')
            =
            \Pr_{\pi,P}[s_h=s,a_h=a,s_{h+1}=s'].
        \]
        %
        Any $x : [H] \times S \times A \times S \mapsto \mathbb{R}$ is an occupancy measure, if and only if
        \begin{alignat}{3}
            &x(h,s,a,s') \ge 0,&
            \qquad 
            &\forall (h,s,a,s') \in [H] \times S \times A \times S,& \nonumber \\
            &\sum_{\mathclap{(s,a,s') \in S \times A \times S}} x(h,s,a,s') = 1,& 
            \qquad 
            &\forall h \in [H],& \nonumber\\
            &\sum_{\mathclap{(a,s') \in A \times S}} x(h+1,s,a,s') = \sum_{\mathclap{(s',a) \in S \times A}} x(h,s',a,s),& 
            \qquad 
            &\forall (s,h) \in S \times [H-1].& \label{eq:omset}
        \end{alignat}
        Indeed, any $x$ that satisfies the conditions above corresponds to an occupancy measure for some policy $\pi$ and transition function $P$, both can easily be extracted from $x$---this correspondence is therefore one-to-one. 
        That is, given an occupancy measure $x$ we can define the corresponding policy and dynamics as follows:
        \begin{equation} \label{eq:oc-pnd}
            \pi^{(x)}(a \mid s,h) = \frac{\sum_{s' \in S} x(h,s,a,s')}{\sum_{(a,s') \in A \times S} x(h,s,a,s')},
            \quad \text{and} \quad
            \widetilde P^{(x)}(s' \mid s,a,h) = \frac{x(h,s,a,s')}{\sum_{s' \in S} x(s,a,h,s')}.
        \end{equation}
        %
        For more on occupancy measures, see \cite{rosenberg2019online}. 

    \paragraph{Self-concordant Barriers and Bregman Divergence.} \label{sec:scb}
    
    We next briefly review self-concordant barrier functions---a fundamental tool in interior-point methods that was also shown to be highly-useful in linear bandit optimization \citep{abernethy2009competing}.
    Self-concordant barriers are discussed in-depth in \cite{nemirovski2004interior}; we give the technical definitions in \cref{app:self} and here focus on some useful properties of such functions that we use.

   
   
   
   
   
   
   
   
    
   
   
   
   
   
   
    
    We consider a $\vartheta$-self-concordant barrier function $R$ over 
    a convex set $\mathcal{S}$. 
    In particular, for a self-concordant barrier $R$,
   
    the function 
    $\|h\|_x = \sqrt{h^\mathsf{T}\nabla^2 R(x)h}$ is a norm, and also $\nabla R : \text{int}(\mathcal{S}) \mapsto \mathbb{R}^d$ is invertible. 
    %
    In addition, an important property of the norm $\|\cdot\|_x$ 
   
   
    is that for any point $y \in \mathbb{R}^d$ and $x \in \text{int}\brk{\mathcal{S}}$,
    \begin{equation} \label{eq:dikininbody}
        \|y-x\|_x < 1 
        ~\implies~ 
        y \in \text{int}\brk{\mathcal{S}}.
    \end{equation}
    
    We define the Bregman divergence with respect to a $\vartheta$-self-concordant barrier $R$ as follows:
    \[ 
        B_R\delimpair{(}{[.]\,\|\,}{)}{y}{x} = R(y) - R(x) - \nabla R(x) \boldsymbol{\cdot} (y-x).
    \]
    The Bregman divergence is always nonnegative: $B_R\delimpair{(}{[.]\,\|\,}{)}{y}{x} \geq 0$ for any $x,y \in \text{int} \brk{\mathcal{S}}$. 
    %
    Moreover, we shall need the following lower bound on the Bregman divergence (see \citealp{nemirovski2004interior}):
    %
    \begin{equation} 
        B_R\delimpair{(}{[.]\,\|\,}{)}{y}{x} 
        \geq 
        \rho \brk{\norm{y-x}_{x}} \quad \text{for} \quad \rho(z) = z - \log(1+z)
        . 
        \label{eq:scbergmanlb}
    \end{equation}
    %
   
   
   
   
    %
   
    We also require the following lemma whose proof is found in \cref{app:proofs}. 
    %
    \begin{lemma} \label{lem:boundbregfromx1}
        Define $\mathcal{S}_\gamma = \{(1-\gamma)x + \gamma x_1 \mid x \in \mathcal{S}\}$ for $x_1 = \argmin_{x \in \mathcal{S}} R(x)$ and some $\gamma \in [0,1]$. 
        Then $B_R\delimpair{(}{[.]\,\|\,}{)}{y}{x_1} \le \vartheta \log(1/\gamma)$ for any $y \in \mathcal{S}_\gamma$.
    \end{lemma}
    
    \paragraph{Online Mirror Descent with Barriers.}
    
    We rely on standard properties of the Online Mirror Descent (OMD) algorithm with a self-concordant barrier function $R$ for a domain $\mathcal{S}$ as regularization, applied to an arbitrary sequence of loss vectors $\ell_1,\ldots,\ell_T \in \mathbb{R}^d$ \citep{abernethy2009competing}.
    Starting from an initial $x_1 \in \mathcal{S}$, OMD makes the following updates for $t=1,\ldots,T$:\footnote{Typically, OMD has an additional projection step when employed on a bounded domain. However, when $R$ is a barrier, such a projection is redundant as the OMD update never steps out of the domain (this is a consequence of \cref{eq:dikininbody}).}
    \begin{align} \label{ALG:OMD}
        x_{t+1} &= \nabla R^{-1} \brk!{ \nabla R(x_t) - \eta_t \ell_t }.
       
       
    \end{align}
    %
   
   
   
   
   
   
   
   
   
   
   
    %
   
   
   
    This version of OMD has the following guarantee (we include a proof in \cref{app:proofs} for completeness); here we use the notation $\norm{\ell}_x^\star = \sqrt{\ell^\mathsf{T} \nabla^2 R(x)^{-1} \ell}$ for $x \in \mathcal{S}$ and $\ell \in \mathbb{R}^d$.
    %
    \begin{lemma} \label{thm:mdbarrier}
        Let $R : \text{int}(\mathcal{S}) \mapsto \mathbb{R}$ be self-concordant and assume that $\eta_t \norm{\ell_t}_{x_t}^\star \leq \tfrac12$ for all $t$.
        Then, for any $u \in \mathcal{S}$,
        \[
            \sum_{t=1}^T \ell_t \boldsymbol{\cdot} (x_t - u)
           
            \le 
            \frac{1}{\eta_1} B_R\delimpair{(}{[.]\,\|\,}{)}{u}{x_1}
            -
            \sum_{t=2}^T \brk3{\frac{1}{\eta_{t-1}} - \frac{1}{\eta_t}} B_R\delimpair{(}{[.]\,\|\,}{)}{u}{x_t}
            + 
            \sum_{t=1}^T \eta_t \brk{\norm{\ell_t}_{x_t}^\star}^2
            .
        \]
    \end{lemma}

    Observe that when the learning rate sequence is strictly increasing, the middle term in the above bound becomes negative and can potentially serve to decrease the regret of OMD, particularly when the divergence $B_R\delimpair{(}{[.]\,\|\,}{)}{u}{x_t}$ is large. This observation will be key to our algorithmic development in \cref{sec:solution-efficient}.
 
\section{Setup and Overview of Results} \label{sec:reduction-main}

    \subsection{Online MDPs with Aggregate Bandit Feedback}
        
        We consider an online version of finite-horizon MDPs in which the interaction between learner and the MDP proceeds for $K$ episodes. Before the interaction begins, the environment assigns a sequence of loss functions $\ell_1,\ldots,\ell_k : [H] \times S \times A \times S \mapsto [0,1]$ one for each episode $k\in [K]$. The choice of loss functions is done in an arbitrary, possibly adversarial, manner.
        
        At the start of each episode $k$ the online algorithm defines a policy $\pi_k$.
        At the end of the episode the online algorithm receives the trajectory realized by $\pi_k$, 
        i.e.,  $(s^k_1, a^k_1, \ldots, s^k_H, a^k_H, s^k_{H+1})$,
        and the aggregate loss incurred during this trajectory with respect to $\ell_k$, i.e., $\sum_{h=1}^{H} \ell_k(h, s^k_h,a^k_h,s^k_{h+1})$.

        We define the regret of the learner over the $K$ episodes as
        \[
            \text{Reg}_K = \sum_{k=1}^K L^{\pi_k, P,\ell_k}  - \min_{\pi} \sum_{k=1}^K L^{\pi, P,\ell_k} ,
        \]
        where the minimum is taken over all policies $\pi$, and we let $\pi^\star$ denote a minimizer.
        %
        The regret can also be written in terms of occupancy measures, by noticing that the expected loss of a policy $\pi$ and transition function $P$ with respect to a loss function $\ell$ is $L^{\pi,P,\ell}=x^{\pi,P}\boldsymbol{\cdot} \ell$.
        %
        Thus, the regret of the learner over the $K$ episodes can be written as:
        \[
            \text{Reg}_K 
            = 
            \sum_{k=1}^K x^{\pi_k, P} \boldsymbol{\cdot} \ell_k - \min_{\pi} \sum_{k=1}^K x^{\pi, P} \boldsymbol{\cdot} \ell_k
            .
        \]
       
        
        The main result of this paper is a computationally-efficient learning algorithm for the setting described above.
        %
        \begin{theorem} \label{thm:main}
            There exists an online learning algorithm for \emph{finite-horizon MDPs with aggregated bandit feedback} that guarantees
            \[
                \mathbb{E} \brk[s]{\text{Reg}_K} = \poly\brk{H,|S|,|A|} \, O(\sqrt{K})
                .
            \]
            Moreover, the per-episode runtime complexity of the algorithm is polynomial in $H, |S|, |A|$, and $K$.
        \end{theorem}
        
        We prove the theorem by efficiently reducing the online MDPs setting to a sequence of instances of a novel setting we term \emph{Distorted Linear Bandits\xspace} (DLB\xspace).
        In what follows, we describe the DLB\xspace setting, the reduction, and  prove the correctness of the reduction. 

\subsection{Distorted Linear Bandits\xspace (DLB\xspace)} \label{sec:blb}

   
    %
    In this game, the learner plays by picking vectors from a compact and convex body $\mathcal{S} \subseteq \mathbb{R}^d$. We assume that $\norm{y}_1 \leq H$ for all $y \in \mathcal{S}$ for some $H>0$. Further, let $\beta>0$ be a bias parameter.
    %
    Learning in the DLB\xspace setting proceed according the following protocol: 
    Initially, the adversary privately chooses a sequence of loss vectors $\ell_1,\ldots,\ell_T$ and a sequence of perturbation vectors $\epsilon_1,\ldots,\epsilon_T \in [0,\beta]^d$.
    Then, at rounds $t = 1,\ldots,T$,
    \begin{enumerate
        \item Learner selects $y_t \in \mathcal{S}$.
        \item Adversary picks $z_t \in \mathbb{R}^d$, where $\norm{z_t}_1 \le H$ such that $\|z_t - y_t\|_1 \leq \min\{\abs{z_t \boldsymbol{\cdot} \epsilon_t}, \abs{y_t \boldsymbol{\cdot} \epsilon_t} \}$.
        \item A random $\hat z_t$ is sampled such that $\mathbb{E}_t \brk[s]{\hat z_t \mid z_t} = z_t$ and $\norm{\hat z_t}_1 \le H$, where $\mathbb{E}_t$ denotes expectation conditioned on all randomness prior to round $t$.
        \item The action $\hat z_t$ is played; the learner suffers and observes the loss $\ell_t \boldsymbol{\cdot} \hat z_t$; the learner additionally observes $\hat z_t$ and $\epsilon_t$.
    \end{enumerate}
    %
    We emphasize that the $z_t$ are arbitrary and can be chosen in an adaptive manner after the learner chooses $y_t$. Note, however, that we assume that the loss vectors (as well as the perturbation vectors) are chosen before the game starts; namely, the adversary is oblivious.
    
    We define the regret in the DLB\xspace setting as follows: 
    \[
        \text{Reg}_T = \sum_{t=1}^T \hat z_t \boldsymbol{\cdot} \ell_t - \min_{z \in \mathcal{S}} \sum_{t=1}^T z \boldsymbol{\cdot} \ell_t.  
    \]
    %
    The learner's goal is therefore to minimize the losses attained by the perturbations $\hat z_1, \ldots, \hat z_T$ of the  actions   $y_1, \ldots, y_T$ chosen by the learner. Clearly, the regret necessarily scales with the magnitudes of $\epsilon_1, \ldots, \epsilon_T$, and our regret bounds will ultimately depend on a parameter $B$ that upper bounds the magnitude of the perturbations via the quantity $\sum_{t=1}^T (\hat z_t \boldsymbol{\cdot} \epsilon_t)^2$.
    %
    The following theorem is the main technical result of our work.
    
    \begin{theorem} \label{thm:blbregret}
        There exists an efficient (poly-time) online learning algorithm for the DLB\xspace setting whose regret is at most
        $
            \poly(H, d, \beta, B) \, O(\sqrt{T}).
        $
    \end{theorem}
    
    We prove this theorem by showing two online learning algorithms (one is computationally-efficient; the other is not) in \cref{sec:blb-algorithms}. We conclude this current section by describing the reduction from online MDPs with aggregate bandit feedback to DLB\xspace.

\subsection{The Reduction} \label{sec:reduction}

    We now show how to reduce the  MDP with aggregate feedback problem to instances of DLB\xspace described above (proofs of results of this section appear in \cref{app:proofs}.)
    Our algorithm for learning  MDPs with aggregate feedback is depicted in detail in \cref{app:reduction-algo}, and here we give a verbal description of the algorithm. The algorithm assumes the existence of a computationally-efficient online learning algorithm for DLB\xspace with $O(\sqrt{T})$ regret which exists due to \cref{thm:blbregret}.
    
    The algorithm partitions the $K$ episodes into epochs, where  epoch $i$ contains episodes $k_i$ through $k_{i+1}-1$  ($k_1 = 1$). Each epoch ends whenever the number of visits to some state-action pair $s,a$ at some time step $h$ is doubled. Thus, the total number of epochs is at most $2 H |S| |A| \log K$. 
    
    In epoch $i$, we produce an empirical estimate of the transition probabilities $\widehat P$ based on all observations prior to epoch $i$. We apply a high probability argument to bound the estimation error $P$ of the dynamics as: $\norm{\widehat P(\cdot \mid s,a,h) - P(\cdot \mid s,a,h)}_1 \le \epsilon_i(s,a,h)/H$ for a confidence parameter $\epsilon_i : S \times A \times [H] \mapsto [0, \beta]$ associated with epoch $i$. ($\epsilon_i(s,a,h)$ decreases as a function of the number of times each $(s,a,h)$ has been visited up to epoch $i$.)
    
    We fix a convex and compact $\mathcal{S}_i$ to be the set of all feasible occupancy measures based on our current estimate of the dynamics of the MDP. We claim that in each epoch, the setting admits to the distorted linear bandits\xspace problem.
    %
    Indeed, we show that with high probability, $\mathcal{S}_i$ contains $x^{\pi^\star, P}$---the occupancy measure associated with the optimal policy and the true dynamics.
    %
    Now, throughout epoch $i$, for $k = k_i,\ldots,k_{i+1}-1$:
    %
    \begin{enumerate
      \item Learner picks a policy $\pi_k$ associated with some occupancy measure $y_k \in \mathcal{S}_i$.
      \item $\pi_k$ is played on the true MDP and the learner observes a trajectory $\hat z_k$, such that $\hat z_k(h,s,a,s') = 1$ iff the trajectory passed through state $s$ at time $h$, played action $a$ and transitioned to state $s'$. Otherwise $\hat z_k(h,s,a,s') = 0$. The learner suffers and observes the loss of $\ell_k \boldsymbol{\cdot} \hat z_k$.
      \item Let $z_k$ be the occupancy measure of $\pi_k$ and the true dynamics $P$; then $\mathbb{E}[\hat z_k \mid z_k] = z_k$. We prove that $\norm{z_k-y_k}_1 \le \min\{\epsilon_i \boldsymbol{\cdot} z_t, \epsilon_i \boldsymbol{\cdot} y_t\}$.
    \end{enumerate}
    %
    Moreover, we give a bound of $\sum_{k=k_i}^{k_{i+1}-1} (\epsilon_i \boldsymbol{\cdot} \hat z_k)^2 = \widetilde O\brk{H^4 |S|^2 |A|}$ as required by the DLB\xspace setting.
    
    We consequently apply the DLB\xspace algorithm to obtain a regret bound of $O(\sqrt{k_{i+1}-k_i}) = O(\sqrt{K})$ in each epoch, and as the number of epochs is only at most $O(\log K)$ this gives an overall regret bound of $\widetilde O(\sqrt{K})$ as required.
    The complete proof of this claim appears in \cref{app:proofs}. The
    analysis of the running time of the algorithm is found in \cref{app:efficientreduction}. 

\section{Algorithms for Distorted Linear Bandits\xspace}
\label{sec:blb-algorithms}

In this section we prove \cref{thm:blbregret} by presenting our online algorithms for the DLB\xspace problem.
The difficulty of this setting lies in the fact that the main mechanism to cope with lack of information in bandit optimization is to construct unbiased estimates of the loss vectors. In the DLB\xspace setting this is impossible to do since the actions chosen by the learner are shifted by the adversary. 
Nevertheless, having $\sum_{t=1}^T (\hat z_t \boldsymbol{\cdot} \epsilon_t)^2$ bounded, intuitively means that the estimation bias at the actions played by the learner is bounded in an amortized sense---a useful property that we utilize in our algorithms.

\subsection{Simple Approach via Optimism}
\label{sec:solution-optimism}

Our first algorithm is based on what is arguably the most straightforward approach to the problem: construct an ``optimistic'' estimator to the player's loss---one whose expectation underestimates the loss of all actions at a given round, yet is sufficiently accurate in estimating the player's loss at the same round---and feed it to a standard bandit linear optimization algorithm. 
However, as we show in this section, such a loss estimator becomes a non-convex (in fact, concave) function of the played action, thus overall this approach leads to a computationally inefficient algorithm.


Throughout this section, we assume that the decision set $\mathcal{S}$ is finite of size $O((H T)^d)$; since for now we are not bound by computational complexity considerations, if $\mathcal{S}$ is a larger (or infinite) set we may replace $\mathcal{S}$ with a $1/(HT)$-net of $\mathcal{S}$, which has the required size.
The algorithm we describe below (\cref{alg:inefficient}) assumes as input an exploration distribution $\mu$ over the set $\mathcal{S}$, such that for $y \sim \mu$ it holds that $\mathbb{E}[yy^\mathsf{T}] \succeq \lambda I$ for a constant $\lambda > 0$. 
Standard techniques in linear bandit optimization (e.g., \citealp{bubeck2012towards,hazan2016volumetric}) show that under fairly general conditions on $\mathcal{S}$, one can pick an exploration distribution $\mu$ so as $\lambda = \Omega(1/\sqrt{d})$.%
\footnote{Some of these techniques rely on solving intractable optimization problems, but recall that in the context of this section we are not concerned by the computational complexity of the resulting algorithm.}

\begin{algorithm}[ht]
    \caption{Distorted Linear Bandits\xspace via Optimistic Biases}
    \begin{algorithmic}[1]
        \STATE {\bf input:} $\eta > 0$, $\gamma > 0$, exploration distribution $\mu$.
        \STATE {\bf initialize:} $w_1(y) = 1$ for all $y \in \mathcal{S}$.
        \FOR{$t = 1,\ldots,T$}
            \STATE {\bf define} probability density $p_t \propto w_t$, and let $q_t = (1-\gamma)p_t + \gamma \mu$.
            \STATE {\bf sample} point $y_t \sim q_t$ in the domain $\mathcal{S}$. 
            \STATE {\bf adversary} chooses $z_t$ such that $\norm{z_t-y_t}_1 \le \min\brk[c]{\abs{y_t \boldsymbol{\cdot} \epsilon_t}, \abs{z_t \boldsymbol{\cdot} \epsilon_t}}$, and plays $\hat z_t$ where $\mathbb{E}_t \brk[s]{\hat z_t \mid z_t} = z_t$.
            \STATE {\bf observe} $\epsilon_t$ and loss $\ell_t \boldsymbol{\cdot} \hat z_t \in [0,H]$.
            \STATE {\bf compute} the second moment of $y_t$:
            $
                M_t = \mathbb{E}_t[y_t y_t^\mathsf{T} ].
            $
            \STATE {\bf compute} $\hat\ell_t = (\ell_t \boldsymbol{\cdot} \hat z_t) M_t^{-1} y_t$ 
            and $\tilde\ell_t(y) = \hat\ell_t \boldsymbol{\cdot} y - \sqrt{d} \, \norm{y}_{M_t^{-1}} \norm{\epsilon_t}_{M_t}$.
            
            \STATE {\bf update} $w_{t+1}(y) = w_t(y) \cdot
            \exp\brk{ -\eta \tilde\ell_t(y)}, \qquad \forall ~ y \in \mathcal{S}$. 
        \ENDFOR
    \end{algorithmic}
    \label{alg:inefficient}
\end{algorithm}

The algorithm relies on a standard estimator $\hat\ell_t = (\ell_t \boldsymbol{\cdot} \hat z_t) M_t^{-1} y_t$ to estimate the loss vector $\ell_t$.
Note that if it were that $z_t=y_t$ then this would have been an unbiased estimator for the loss, i.e., $\mathbb{E}_t [\hat\ell_t]=\ell_t$. 
However, due to the adversarial perturbations $z_t$ might be shifted away from the intended $y_t$. We thus modify the estimator to account for this shift and make it ``optimistic,'' in the sense that its expectation is a lower bound on the real loss function.
Given these corrected estimates, the rest of the algorithmic development follows standard lines in the linear bandit optimization literature~\citep{dani2008price,bubeck2012towards}.

Concretely, we define the following \emph{bias-corrected} loss functions:
\begin{align*}
    \tilde\ell_t(y)
    =
    \hat\ell_t \boldsymbol{\cdot} y - \sqrt{d} \, \norm{y}_{M_t^{-1}} \norm{\epsilon_t}_{M_t}
    ,
    \qquad
    \forall ~ t \in [T], y \in \mathcal{S}
    ~.
\end{align*}
Then, the algorithm essentially performs multiplicative-weights updates on the modified loss functions $\tilde\ell_t(y)$, which can be seen to be a \emph{concave} function of $y$.
In general, it is a hard problem to sample from the resulting distributions $q_t$ given that these losses are concave. (If, on the other hand, they were convex, then the resulting distributions would have been log-concave for which efficient sampling algorithms are well-known.)
Therefore, the algorithm is computationally inefficient.

We prove that \cref{alg:inefficient} provides the following regret guarantee.

\begin{theorem} \label{thm:optimismmain}
    Set $\eta = (2H\beta d)^{-1} \sqrt{\log |\mathcal{S}| /T}$, $\gamma = 2H^2 (H + \beta\sqrt{d}) \eta/\lambda$. 
    Then, given that $B \geq \sum_{t=1}^T (\hat z_t \boldsymbol{\cdot} \epsilon_t)^2$ (almost surely),  for any $y^\star \in \mathcal{S}$, \cref{alg:inefficient} satisfies that
    \begin{align*}
        \mathbb{E}\brk[s]4{ \sum_{t=1}^T \ell_t \boldsymbol{\cdot} (\hat z_t - y^\star) }
        = 
        \widetilde O\brk*{ H\beta d + \beta d \sqrt{B} + \frac{H^3}{\beta\lambda d} + \frac{H^2}{\lambda \sqrt{d}} } \sqrt{T}
        ,
    \end{align*}
    provided that $\beta \ge 1$ and $T \ge \ipfrac{4 H^2 (H + \beta \sqrt{d})^2 \log |\mathcal{S}|}{\lambda^2 \beta^2 d^2}$.
\end{theorem}

\noindent
We only sketch the proof here, deferring details and precise bounds to \cref{app:proofs}.

\begin{proof}[(sketch)]
    We begin by showing that $\tilde \ell_t$ is indeed an underestimate of the true loss (see \cref{lem:loss-underestimate} below):
    \[
        \mathbb{E}_t[\tilde\ell_t(y)] \leq \ell_t \boldsymbol{\cdot} y \quad \text{for any} \quad y \in \mathcal{S}
        .
    \]
    %
    For the converse direction, we show that in expectation over the learner's decision, $\tilde \ell_t$ is close to $\ell_t$ in the following sense:
    \[
        \mathbb{E}_t\brk[s]*{ \sum_{y \in \mathcal{S}} p_t(y) \tilde\ell_t(y) } 
        \ge 
        \mathbb{E}_t \brk[s]{\ell_t \boldsymbol{\cdot} \hat z_t} - \gamma H - 5d \norm{\epsilon_t}_{M_t}
        .
    \]
    %
    With these two results at hand, we argue that the regret of \cref{alg:inefficient} is bounded by the regret of the \textsc{Multiplicative Weights} updates, plus an additive error term that scales with the perturbations~$\epsilon_t$:
    \begin{align}
        \mathbb{E}\brk[s]4{ \sum_{t=1}^T \ell_t \boldsymbol{\cdot} (\hat z_t - y^\star) }
        \leq
        \mathbb{E}\brk[s]4{ \sum_{t=1}^T \sum_{y \in \mathcal{S}} p_t(y) \brk!{ \tilde\ell_t(y) - \tilde\ell_t(y^\star) } } 
        +
        \gamma H T
        +
        5d\,\mathbb{E}\brk[s]4{ \sum_{t=1}^T \norm{\epsilon_t}_{M_t} }
        .
        \label{eq:optimistic-regret-relation}
    \end{align}
    
    Next, we apply a standard second-order regret bound of \textsc{Multiplicative Weights}
   
    to obtain the following:
    \begin{align*}
        \sum_{t=1}^T \sum_{y \in \mathcal{S}} p_t(y) \brk!{ \tilde\ell_t(y) - \tilde\ell_t(y^\star) }
        \leq
        \frac{\log\abs{\mathcal{S}}}{\eta} + \eta \sum_{y \in \mathcal{S}} p_t(y) \brk!{\tilde\ell_t(y)}^2
        ,
    \end{align*}
    and we bound the term 
    $
        \mathbb{E}_t \brk[s]{\sum_{y \in \mathcal{S}} p_t(y) \brk{\tilde\ell_t(y)}^2}
        \le
        8(H\beta d)^2
    $ 
    using simple algebra.
    
    The theorem is now given by combining the second-order regret bound above together with \cref{eq:optimistic-regret-relation}, and by bounding the bias terms using the DLB\xspace setting assumptions, as
    \begin{align*}
        \mathbb{E}\brk[s]4{ \sum_{t=1}^T \norm{\epsilon_t}_{M_t} }
        \le
        2\beta \sqrt{B T}
        .
        &\qedhere
    \end{align*}
\end{proof}

We now prove that as mentioned, the expectation of $\tilde \ell_t$ is an underestimate of the true loss.

\begin{lemma} \label{lem:loss-underestimate}
    $\mathbb{E}_t[\tilde\ell_t(y)] \leq \ell_t \boldsymbol{\cdot} y$ for any $y \in \mathcal{S}$.
\end{lemma}

\begin{proof}
    Observe that
    \begin{align*}
        \mathbb{E}_t[ \hat\ell_t ]
        &=
        \mathbb{E}_t[ (\ell_t \boldsymbol{\cdot} z_t) M_t^{-1} y_t]
        \\
        &=
        \mathbb{E}_t[M_t^{-1} y_t y_t^\mathsf{T} \ell_t] + \mathbb{E}_t[M_t^{-1} y_t (z_t-y_t) \boldsymbol{\cdot} \ell_t]
        \\
        &=
        \ell_t + M_t^{-1} \mathbb{E}_t[y_t (z_t-y_t) \boldsymbol{\cdot} \ell_t]
        .
    \end{align*}
    %
    Our assumptions imply that $\abs{(z_t-y_t) \boldsymbol{\cdot} \ell_t} \leq
    \norm{z_t-y_t}_1 \norm{\ell_t}_\infty \leq \abs{y_t \boldsymbol{\cdot} \epsilon_t}$.
    Thus, by two applications of Cauchy-Schwartz, for any $y \in \mathcal{S}$ we
    obtain 

    \begin{align} \label{eq:tildell}
        \begin{aligned}
        \mathbb{E}_t [ \abs{(\hat\ell_t - \ell_t) \boldsymbol{\cdot} y} ]
           &=
       
       
       
        \mathbb{E}_t\brk[s]!{ \abs{y^\mathsf{T} M_t^{-1} y_t} \cdot \abs{(z_t-y_t) \boldsymbol{\cdot} \ell_t} }
        \\
        &\leq
        \norm{y}_{M_t^{-1}} \mathbb{E}_t\brk[s]!{ \norm{y_t}_{M_t^{-1}} \abs{y_t \boldsymbol{\cdot} \epsilon_t} }
        \\
        &\leq
        \norm{y}_{M_t^{-1}} \sqrt{ \mathbb{E}_t\brk[s]{ \norm{y_t}_{M_t^{-1}}^2 } \, \mathbb{E}_t\brk[s]{ (y_t \boldsymbol{\cdot} \epsilon_t)^2 } }
        \\
        &=
        \norm{y}_{M_t^{-1}} \sqrt{ \mathbb{E}_t\brk[s]{ y_t^\mathsf{T} M_t^{-1} y_t } } \sqrt{ \epsilon_t^\mathsf{T} \mathbb{E}_t[y_t y_t^\mathsf{T}]  \epsilon_t  }
        \\
        &=
        \sqrt{d} \norm{y}_{M_t^{-1}} \norm{\epsilon_t}_{M_t}
        .
        \end{aligned}
    \end{align}
    This means that
    \begin{align*}
        \mathbb{E}_t[\tilde\ell_t(y) - \ell_t \boldsymbol{\cdot} y]
        =
        \mathbb{E}_t[(\hat\ell_t-\ell_t) \boldsymbol{\cdot} y] - \sqrt{d} \norm{y}_{M_t^{-1}} \norm{\epsilon_t}_{M_t}
        \leq 
        0
    \end{align*}
    which proves that $\mathbb{E}[\tilde\ell_t(y)] \leq \ell_t \boldsymbol{\cdot} y$ for any $y \in
    \mathcal{S}$.
\end{proof}


\subsection{Efficient Approach via OMD with Increasing Learning Rates}
\label{sec:solution-efficient}

Our previous algorithm enjoys an $\widetilde O(\sqrt{T})$ regret bound, but it is inherently computationally inefficient. 
In this section we take a different approach that leads to an algorithm with $\widetilde O(\sqrt{T})$ regret, but one that can also be implemented efficiently. 

\begin{algorithm}[ht]
    \caption{Distorted Linear Bandits\xspace via Increasing Learning Rates}
    \label{alg:increasinglearningrates}
    \begin{algorithmic}[1]
        \setcounter{ALC@unique}{0}
        \STATE {\bf input}: $\eta_0 > 0$, $\vartheta$-self-concordant barrier $R : \text{int}\brk{\mathcal{S}} \mapsto \mathbb{R}$.
        \STATE {\bf init}: $x_1 = \argmin_{x \in \mathcal{S}} R(x)$.
        \FOR{$t = 1,\ldots,T$}
            \STATE {\bf sample} $u_t$ uniformly at random from the unit sphere of $\mathbb{R}^d$.
            \STATE {\bf predict} $y_t = x_t + \nabla^2 R(x_t)^{-1/2} u_t$. \label{ln:yt}
            \STATE {\bf adversary} chooses $z_t$ such that $\norm{z_t-y_t}_1 \le \min\brk[c]{\abs{y_t \boldsymbol{\cdot} \epsilon_t}, \abs{z_t \boldsymbol{\cdot} \epsilon_t}}$, and plays $\hat z_t$ where $\mathbb{E}_t \brk[s]{\hat z_t \mid z_t} = z_t$.
            \STATE {\bf observe} $\hat z_t$, $\epsilon_t$, and loss $\ell_t \boldsymbol{\cdot} \hat z_t \in [0,H]$.
            \STATE {\bf construct} $\tilde \ell_t = d (\ell_t \boldsymbol{\cdot} \hat z_t) \nabla^2 R(x_t)^{1/2} u_t$. \label{ln:estimator}
            \STATE {\bf update} $\eta_t^{-1} = \eta_{t-1}^{-1} - 2 d \, |\hat z_t \boldsymbol{\cdot} \epsilon_t|$. \label{ln:increase-lr}
            \STATE {\bf set} $x_{t+1} = \nabla R^{-1} \brk{\nabla R(x_t) - \eta_t \tilde \ell_t}$. \label{ln:update}
        \ENDFOR
    \end{algorithmic}
\end{algorithm}

\cref{alg:increasinglearningrates} is based on Online Mirror Descent with a self-concordant barrier $R$ as a regularizer \citep{abernethy2009competing}.
The algorithm maintains a sequence of points $x_1,\ldots,x_T \in \mathcal{S}$. 
In \cref{ln:yt}, the algorithm makes a prediction $y_t$ by sampling uniformly at random from the ellipsoid $\{y : \norm{y - x_t}_{x_t} \le 1\}$, known as the \emph{Dikin Ellipsoid} associated with $R$ at $x_t$, that is always contained in $\mathcal{S}$ (this follows from \cref{eq:dikininbody}).
Then, according to the DLB\xspace protocol, the algorithm receives $\epsilon_t$, $\hat z_t$ and loss $\ell_t \boldsymbol{\cdot} \hat z_t$ such that $z_t = \mathbb{E}_t[\hat z_t \mid z_t]$ where $z_t$ is a perturbation of $y_t$. 

The algorithm proceeds to construct an estimator $\tilde \ell_t$ of the loss vector $\ell_t$ in \cref{ln:estimator}. Note that if we replace $\hat z_t$ with $y_t$ in \cref{ln:estimator}, then $\tilde \ell_t$ would be an unbiased estimator. 
However, as this is not the case, the algorithm must mitigate the bias in the $\tilde \ell_t$, and does that by increasing its learning rate according to the perturbation magnitude $|\hat z_t \boldsymbol{\cdot} \epsilon_t|$ (\cref{ln:increase-lr}).
Finally, in \cref{ln:update}, the algorithm performs the mirror descent update.%

\cref{alg:increasinglearningrates} can be implemented efficiently as long as $\mathcal{S}$ is not degenerate (namely, $\mathcal{S}$ is compact and has volume in $\mathbb{R}^d$, and thus admits a proper self-concordant barrier $R$) and as long as gradients and Hessians of $R$ can be computed efficiently. 
We defer a more detailed discussion of implementation issues to \cref{app:efficientreduction}.

Our main result regarding the algorithm is as follows.

\begin{theorem} \label{thm:inclrregret}
    \cref{alg:increasinglearningrates} with 
    $
        \eta_0 
        = 
        \widetilde\Theta\brk{ 
        \vartheta / \brk{d \vartheta \sqrt{B T} + d H \sqrt{\vartheta T}}}
    $ 
    provides the following regret guarantee, for any $y^\star \in \mathcal{S}$:
   
   
   
   
   
   
   
   
    \[
        \mathbb{E} \brk[s]4{\sum_{t=1}^T (\hat z_t - y^\star) \boldsymbol{\cdot} \ell_t}
        =
       
       
       
       
       
       
        \widetilde O\brk!{
        d \vartheta \sqrt{B T}
        + 
        d H \sqrt{\vartheta T}}
        ,
    \]
    provided that $B \geq \max\{\sum_{t=1}^T (\hat z_t \boldsymbol{\cdot} \epsilon_t)^2, H\}$ (almost surely).
\end{theorem}

Here we sketch the proof of \cref{thm:inclrregret} highlighting the key ideas; the complete proof and precise bounds can be found in \cref{app:proofs}.

\begin{proof}[(sketch)]
    The first part of the proof is straightforward.
    We split the regret into three terms:
    \begin{align}
        \mathbb{E} \brk[s]4{\sum_{t=1}^T (\hat z_t-y^\star)\boldsymbol{\cdot} \ell_t}
       
       
        =
        \mathbb{E} \brk[s]4{\sum_{t=1}^T (z_t-x_t)\boldsymbol{\cdot} \ell_t}
        +
        \mathbb{E} \brk[s]4{\sum_{t=1}^T (x_t-y^\star_\gamma)\boldsymbol{\cdot} \ell_t}
        +
        \mathbb{E} \brk[s]4{\sum_{t=1}^T (y^\star_\gamma-y^\star)\boldsymbol{\cdot} \ell_t}
        ,
        \label{eq:regretdecomp}
    \end{align}
    where $y^\star_\gamma = (1-\gamma) y^\star + \gamma x_1 \in \mathcal{S}_\gamma$ for sufficiently small $\gamma$.
    (Following a standard technique, we introduce $y^\star_\gamma$ as otherwise we would eventually have to bound $B_R\delimpair{(}{[.]\,\|\,}{)}{y^\star}{x_1}$ which might be arbitrarily large; by introducing $y^\star_\gamma$, we instead would have to bound $B_R\delimpair{(}{[.]\,\|\,}{)}{y^\star_\gamma}{x_t}$, which is bounded by \cref{lem:boundbregfromx1}.)
   
    The first summand in \cref{eq:regretdecomp} pertains to the bias generated by the perturbation of $y_t$ to $z_t$, and is bounded by $\sqrt{B T}$;
    the third summand bounds the loss difference between that of $y^\star$ and of $y^\star_\gamma$, and is bounded by $2 \gamma H T$. All of these quantities are  $\widetilde O\brk!{ d \vartheta \sqrt{B T} + d H \sqrt{\vartheta T}}$.
    
    The heart of the proof focuses on bounding the second summand.
    To this end, we apply \cref{lem:boundlossbias} (see below) to bound the instantaneous regret of the algorithm at each time step $t$, by the instantaneous regret using the loss estimator $\tilde \ell_t$ plus an additional bias term that scales with $\norm{x_t - y^\star_\gamma}_{x_t}$. This results with
    \begin{equation} \label{eq:specificlossbias}
        (x_t - y^\star_\gamma) \boldsymbol{\cdot} \ell_t 
        \le 
        \mathbb{E}_t \brk[s]{(x_t - y^\star_\gamma) \boldsymbol{\cdot} \tilde \ell_t} 
        + 
        d \norm{x_t - y^\star_\gamma}_{x_t} \mathbb{E}_t \brk[s]{\abs{\hat z_t \boldsymbol{\cdot} \epsilon_t}},
    \end{equation}
    and we proceed in bounding $\mathbb{E} [\sum_{t=1}^T \mathbb{E}_t \brk[s]{(x_t - y^\star_\gamma) \boldsymbol{\cdot} \tilde \ell_t} ] = \mathbb{E} [\sum_{t=1}^T (x_t - y^\star_\gamma) \boldsymbol{\cdot} \tilde \ell_t ]$. 
    %
    Since the algorithm is taking \textsc{OMD} steps with loss vectors $\tilde\ell_t$, we can apply \cref{thm:mdbarrier} to get
    \[
        \mathbb{E} \brk[s]4{\sum_{t=1}^T (x_t - y^\star_\gamma) \boldsymbol{\cdot} \tilde \ell_t} 
        \le
        \mathbb{E} \brk[s]4{
            \frac{1}{\eta_1} B_R\delimpair{(}{[.]\,\|\,}{)}{y^\star_\gamma}{x_1}
            -
            \sum_{t=2}^T \brk3{\frac{1}{\eta_{t-1}} - \frac{1}{\eta_t}} B_R\delimpair{(}{[.]\,\|\,}{)}{y^\star_\gamma}{x_t}
            + 
            \sum_{t=1}^T \eta_t (\|\tilde \ell_t\|_{x_t}^\star)^2
        }.
    \]
    %
    Handling the first and third terms is standard (following \citealp{abernethy2009competing}), and they are shown to be bounded by $O((\vartheta/\eta_0) \log(1/\gamma))$ and $O(\eta_0 d^2 H^2 T)$ respectively, both are $\widetilde O\brk{ d \vartheta \sqrt{B T} + d H \sqrt{\vartheta T}}$ for our choice of parameters.
    The middle term in the bound above is what enables the algorithm to compensate for the bias in the loss estimation by employing an increasing learning rate schedule.
    Indeed, together with \cref{eq:specificlossbias} we obtain
    \begin{align}
    \begin{aligned}
        \mathbb{E} \brk[s]4{\sum_{t=1}^T (x_t - y^\star_\gamma) \boldsymbol{\cdot} \ell_t}
        \le\;
        &d \, \mathbb{E}\brk[s]*{ \sum_{t=1}^T \norm{x_t - y^\star_\gamma}_{x_t} \abs{\hat z_t \boldsymbol{\cdot} \epsilon_t} }
        -
        \mathbb{E}\brk[s]*{ \sum_{t=2}^T \brk3{\frac{1}{\eta_{t-1}} - \frac{1}{\eta_t}} B_R\delimpair{(}{[.]\,\|\,}{)}{y^\star_\gamma}{x_t} }
        \\
        &+ 
        \widetilde O\brk!{ d \vartheta \sqrt{B T} + d H \sqrt{\vartheta T}}
        . 
    \end{aligned}
    \label{eq:xxxxx}
    \end{align}
    %
    The key observation is that the divergence $B_R\delimpair{(}{[.]\,\|\,}{)}{y^\star_\gamma}{x_t}$ here is directly related to the bias term $\norm{y^\star_\gamma - x_t}_{x_t}$ via \cref{lem:boundbregfromxt} (found below), as
    $$
        B_R\delimpair{(}{[.]\,\|\,}{)}{y^\star_\gamma}{x_t}
        \geq 
        \tfrac12 \norm{y^\star_\gamma - x_t}_{x_t} - 1
        .
    $$
    %
    Now, with our particular setting of learning rates (\cref{ln:increase-lr}) the second term in \cref{eq:xxxxx} is upper bounded by 
    $
        -d \sum_{t=1}^T \norm{y^\star_\gamma - x_t}_{x_t} \mathbb{E}_t[|\hat z_t \boldsymbol{\cdot} \epsilon_t|] 
        + O((\vartheta/\eta_0) \log(1/\gamma))
    $
    (in expectation), which precisely cancels out the first summation over the bias terms and gives the $\widetilde O\brk!{ d \vartheta \sqrt{B T} + d H \sqrt{\vartheta T}}$ regret bound.
\end{proof}

The following lemma bounds the instantaneous regrets suffered by the algorithm, by the algorithm's estimates of the instantaneous regret plus an additive bias term that scales as $\norm{x_t-x}_{x_t}$.

\begin{lemma} \label{lem:boundlossbias}
    Let $x \in \mathcal{S}$. Then,
    $
        (x_t - x) \boldsymbol{\cdot} \ell_t 
        \le 
        \mathbb{E}_t \brk[s]{(x_t - x) \boldsymbol{\cdot} \tilde \ell_t} 
        + 
        d \norm{x_t - x}_{x_t} \mathbb{E}_t \brk[s]{\abs{\hat z_t \boldsymbol{\cdot} \epsilon_t}}.
    $
\end{lemma}

\begin{proof}
Recall that $x_t$ is determined given the randomness up to time $t$.
We have that 
    \begin{align*}
        \mathbb{E}_t \brk[s]1{(x_t - x) \boldsymbol{\cdot} \tilde \ell_t}
        &=
        \mathbb{E}_t \brk[s]1{(x_t - x) \boldsymbol{\cdot} d \brk{\ell_t \boldsymbol{\cdot} \hat z_t} \nabla^2 R(x_t)^{1/2} u_t} \\
        &=
        \mathbb{E}_t \brk[s]1{(x_t - x) \boldsymbol{\cdot} d \brk1{\ell_t \boldsymbol{\cdot} \mathbb{E}_t \brk[s]{\hat z_t \mid z_t}} \nabla^2 R(x_t)^{1/2} u_t} \\
        &=
        \mathbb{E}_t \brk[s]1{(x_t - x) \boldsymbol{\cdot} d \brk{\ell_t \boldsymbol{\cdot} z_t} \nabla^2 R(x_t)^{1/2} u_t} \\
        &=
        \underbrace{\mathbb{E}_t \brk[s]1{(x_t - x) \boldsymbol{\cdot} d \brk{\ell_t \boldsymbol{\cdot} x_t} \nabla^2 R(x_t)^{1/2} u_t}}_{(1)}
        +
        \underbrace{\mathbb{E}_t \brk[s]1{(x_t - x) \boldsymbol{\cdot} d \brk1{\ell_t \boldsymbol{\cdot} \brk{y_t - x_t}} \nabla^2 R(x_t)^{1/2} u_t}}_{(2)} \\
        &\qquad -
        \underbrace{\mathbb{E}_t \brk[s]1{(x_t - x) \boldsymbol{\cdot} d \brk1{\ell_t \boldsymbol{\cdot} \brk{y_t - z_t}} \nabla^2 R(x_t)^{1/2} u_t}}_{(3)}.
    \end{align*}
    Next, we analyze each of the three summands above.
    As the only randomness given the history up to time $t$ is in $u_t$, we have
    $
        (1) = 0
    $,
    and as $y_t-x_t = \nabla^2 R(x_t)^{-1/2} u_t$, we have
    \begin{align*}
        (2)
        &=
        \mathbb{E}_t \brk[s]1{(x_t - x) \boldsymbol{\cdot} d \nabla^2 R(x_t)^{1/2} u_t \, \brk{y_t - x_t} \boldsymbol{\cdot} \ell_t} \\
        &=
        \mathbb{E}_t \brk[s]1{(x_t - x) \boldsymbol{\cdot} d \, \nabla^2 R(x_t)^{1/2} u_t u_t^\mathsf{T} \nabla^2 R(x_t)^{-1/2} \ell_t} \\
        &=
        (x_t - x) \boldsymbol{\cdot} d \, \nabla^2 R(x_t)^{1/2} \mathbb{E}_t \brk[s]1{u_t u_t^\mathsf{T}} \nabla^2 R(x_t)^{-1/2} \ell_t \\
        &=
        (x_t - x) \boldsymbol{\cdot} d \, \nabla^2 R(x_t)^{1/2} \boldsymbol{\cdot} \tfrac{1}{d} I \boldsymbol{\cdot} \nabla^2 R(x_t)^{-1/2} \ell_t \\
        &=
        (x_t - x) \boldsymbol{\cdot} \ell_t.
    \end{align*}
    For term (3), two applications of H\"{o}lder's inequality yield
    \begin{align*}
        (3)
        \le
        d \, \mathbb{E}_t \brk[s]1{\norm{x_t - x}_{x_t} \norm{\nabla^2 R(x_t)^{1/2} u_t}_{x_t}^\star  
        \norm{\ell_t}_\infty \norm{y_t - z_t}_1}. 
    \end{align*}
    
    Now, to obtain the lemma, we use our assumption that $\norm{\ell_t}_\infty \le 1$, that
    \[
        \mathbb{E}_t \brk[s]{\norm{y_t - z_t}_1} 
        \le 
        \mathbb{E}_t \brk[s]{\abs{z_t \boldsymbol{\cdot} \epsilon_t}}
        =
        \mathbb{E}_t \brk[s]1{\abs{\mathbb{E}_t \brk[s]{\hat z_t \mid z_t} \boldsymbol{\cdot} \epsilon_t}}
        \le
        \mathbb{E}_t \brk[s]{\abs{\hat z_t \boldsymbol{\cdot} \epsilon_t}},
    \] 
    by Jensen's inequality, and finally
    $
        \norm{R(x_t)^{1/2} u_t}_{x_t}^\star 
        =
        1
    $
    due to \cref{lem:technicalstuff} (see \cref{app:proofs}).
\end{proof}


The next lemma lower bounds the Bregman divergence of any point $x \in \mathcal{S}$ from $x_t$ by an order of their distance in local norm; i.e., $\|x-x_t\|_{x_t}$.

\begin{lemma} \label{lem:boundbregfromxt}
    Let $x \in \mathcal{S}$. Then, 
    $
        B_R\delimpair{(}{[.]\,\|\,}{)}{x}{x_t} 
        \geq 
        \frac{1}{2} \|x-x_t\|_{x_t} - 1.
    $
\end{lemma}

\begin{proof}
    Recall that
    $
        B_R\delimpair{(}{[.]\,\|\,}{)}{x}{x_t} 
        \geq 
        \rho \brk{\|x - x_t\|_{x_t}}
    $ 
    by \cref{eq:scbergmanlb} where $\rho(z)=z-\log (1+z)$.
    Since $\rho \brk{z}$ is convex, we can lower bound
    \[
        \rho \brk{z} 
        \ge 
        \rho \brk{1} + \rho' \brk{1} \boldsymbol{\cdot} \brk{z - 1} 
        =
        \frac{1}{2} - \log(2) + \frac{1}{2} z
        \ge 
        \frac{1}{2} z - 1,
    \]
    which yields the lemma's statement for $z=\|x - x_t\|_{x_t}$. 
\end{proof}

\ifx1\undefined
\else
    \if\arxivver1
        \bibliographystyle{plainnat}
    \fi
\fi
