# Static and Dynamic Measures of Active Music Listening as Indicators of
Depression Risk

###### Abstract

Music, an integral part of our lives, which is not only a source of
entertainment but plays an important role in mental well-being by impacting
moods, emotions and other affective states. Music preferences and listening
strategies have been shown to be associated with the psychological well-being
of listeners including internalized symptomatology and depression. However,
till date no studies exist that examine time-varying music consumption, in
terms of acoustic content, and its association with users’ well-being. In the
current study, we aim at unearthing static and dynamic patterns prevalent in
active listening behavior of individuals which may be used as indicators of
risk for depression. Mental well-being scores and listening histories of 541
Last.fm users were examined. Static and dynamic acoustic and emotion-related
features were extracted from each user’s listening history and correlated with
their mental well-being scores. Results revealed that individuals with greater
depression risk resort to higher dependency on music with greater
repetitiveness in their listening activity. Furthermore, the affinity of
depressed individuals towards music that can be perceived as sad was found to
be resistant to change over time. This study has large implications for future
work in the area of assessing mental illness risk by exploiting digital
footprints of users via online music streaming platforms.

Index Terms: acoustic features, emotion dynamics, naturalistic music
consumption, depression, lastfm

##  1 Introduction

Depression has become the leading disability in the modern world affecting
around $4.4\%$ of the population worldwide by 2015, according to reports from
World Health Organization [1]. There has been a net increase of $18.4\%$ in
the number of people living with depression between 2005 and 2015 [2] and is
only going to increase as a result of the COVID-19 pandemic [3, 4, 5, 6]. This
has made depression an important topic of research associating it to different
behavioral aspects of individuals with major implications on society. Research
has demonstrated that during periods of depression, there is a strong reliance
on listening to music impacting moods, emotions and altering affect states of
an individual [7].

Musical engagement strategies have been linked to measures of ill-health
including internalized symptomatology and depression [8, 9]. It has been found
that using music for rumination, avoidance and mood worsening is an indicator
of risk for depression [10]. To add to this the inability to cease from
repeatedly listening to music which leads to such worsening has also been one
of the representative engagement strategies of individuals at risk for
depression [10]. In terms of musical content, people who are at-risk for
depression demonstrate a liking for sad music [11]. The vast majority of these
studies have relied on self-reported musical consumption data and measures,
typically using standard questionnaires, which may suffer from demand
characteristics and/or social desirability bias. Therefore, in this age of big
data, examining naturally occurring online consumption, especially using
streaming platforms, provides a more ecologically valid reflection of their
true preferences and behaviours [12] and has been proposed as the new frontier
[13].

Studies have emerged that have examined mental well-being using multimedia
content from social networking platforms such as Facebook, Twitter, Instagram
[14, 15, 16, 17, 18]. Till date, Surana et. al [19] has been the only study
that examined association between mental well-being and naturally occurring
music listening habits. They examined online music consumption via the music
streaming platform Last.fm111www.last.fm and associated attributes of the most
listened to music tracks with the respective users’ well-being scores.
Subsequently, the social tags, specifically adjectives and adverbs, associated
with the most frequently listened tracks per user were projected onto the
standard 2-dimensional emotion space, that is Valence-Arousal (VA) model or
the Russell’s Circumplex Model of Affect [19] where Valence represents
pleasantness and Arousal represents energy or activity. In addition, a
3-dimensional emotion model (VAD) was also used with the addition of the
Dominance or perceived intensity dimension and compared results. They found
that individuals at-risk for depression predominantly listen to music which
are socially tagged as being representative of low arousal and negatively
valenced emotion, sadness, and its related terms, such as dead, low,
depressed, repetitive, and miserable. However, solely focusing on social tags
does not yield insights into the acoustic properties of the music. For
example, a heavy metal piece of music with tags labelled as transcendental or
wonderful and a sad love song or ballad with the same tags are different
acoustically but would get clubbed into the same emotion category.
Furthermore, a considerable amount of tracks on online platforms remain
untagged resulting in loss of information. Hence it is important to examine
acoustic features of music and the perceived emotions extracted from them
thereof to get a better understanding of music consumption of individuals at-
risk for depression.

Furthermore, emotions are dynamic processes that fluctuate in response to
environmental demands and regulatory forces [20] and certain patterns or
irregularities with which they fluctuate across time have been associated with
psychological well-being. Higher levels of emotion variability and inertia
have been linked to depression [21, 22]. These fluctuations in the internal
emotion states of individuals might be reflected in their dynamic use of
music. Hence, it is important to investigate time-varying musical consumption.

Figure 1: Methodology

The aim of this study is to characterize online music consumption of
individuals at-risk for depression by analyzing acoustic and emotion-related
features and their dynamic variation. To this end, we analyze naturally
occurring music listening behavior via listening histories of Last.fm users.
We also examine time-varying properties of acoustic and emotion-related
features and associate them with the respective users’ well-being scores
indicative of risk for depression. Based on previous literature we hypothesize
the following Last.fm users who demonstrate high depression risk that is
characterized by low well-being scores:

  * •

greater overall consumption of music, especially music that is perceived as
sad

  * •

higher repetition in music tracks owing to ruminative and repetitive
engagement.

  * •

increased level of variability and/or inertia in terms of the acoustic and
emotion information of music across time

The results are discussed in the context of potential underlying moods or
states.

##  2 Methodology

Figure 1 encapsulates the procedure used in our study and is described as
follows.

###  2.1 Dataset

Data was from the aforementioned Surana et al. [19] study comprising listening
histories of 541 Last.fm users (82 females, mean age = 25.4 years, std = 7.3
years). The respective users’ well-being was measured using standard
diagnostic questionnaire, the Kessler’s Psychological Distress Scale (K10)
[23]. Additionally, the Healthy-Unhealthy music (HUMS) [10] scale was
administered to measure musical engagement which describes music consumption
behavior and indirectly indicates risk for depression, in addition to
personality data. HUMS and personality information have not been used in the
current study, but have been additionally used in the original study [19] to
evaluate internal consistency, which was found to be high. K10 scores
demonstrated high reliability (cronbach alpha $=0.91$). The participants’
listening histories were extracted for a duration of 6 months centered (± 3
months) around the time they filled the K10 questionnaire.

###  2.2 Feature Extraction

In order to extract acoustic features from a track we used the
Spotify222www.spotify.com public API. Spotipy333developer.spotify.com package
was employed to search for each track in Spotify database and retrieve the
values for 10 features that Spotipy provides. Eight of these were audio
features which comprised danceability, loudness, speechiness, acousticness,
instrumentalness, liveness, tempo, and mode. All the features take continuous
values except mode which is binary (0:major, 1:minor). Additional two emotion
features representing the valence and energy/arousal were also retrieved. We
further categorized each track into one of the four quadrants of the
2-dimensional VA space [24]. The first quadrant loosely translates to the
emotion category representing happiness, the second quadrant to anger, the
third to sadness and the fourth to tenderness, as shown in Figure 2[24]. For
each quadrant we calculated a quadrant prevalance score (QPS) which is
calculated as the proportion of tracks in the respective quadrants in each
user’s listening history. As mentioned before, individuals at risk for
depression have an inclination for music representing sadness [19]. Hence, in
order to get a bird’s eye-view of the acoustic features associated with
individuals at-risk when compared to no risk for depression, we calculated
static features that comprise mean score for the eight audio features as well
as the QPS over each user’s entire listening history which we term as summary
features hereon.

####  2.2.1 Session-based feature generation

Since we aimed to capture the changes in participants’ audio features and
emotions over time, we defined time resolution based on sessions. A session
was defined as a period of continuous listening activity, with a subsequent
session occurring after an inactivity of at least two hours [25]. Further, in
each session, audio features for all the tracks were averaged to denote the
value of that feature for the respective session. Also, the QPS for the four
quadrants were computed per session for each user. Thus, we obtained time-
varying values for both, audio and QPS features, for each user over his/her
6-month listening period. The reason for using a smaller time
interval/resolution based on sessions as opposed to larger intervals like days
or weeks is due to the fact that emotions are more transient and short-lived
than mood states which may span for days [26]. For example, continued music
consumption across sessions with certain features may result in greater
successive session-based QPS in certain quadrants and might reflect underlying
moods. For example, a user might continuously listen to sad music, the
acoustic features of which might be predominant in say the third quadrant
representing sadness, and hence may be indicative of underlying risk for
depression based on aforementioned previous literature. Furthermore, we
extracted additional measures that capture such dynamic behavior which provide
a better understanding of users’ mood shifts characterized by variability and
inertia. These additional dynamic measures are explained in following section.

Figure 2: Four quadrants of Valence-Arousal space representing four emotional
states.

Finally, since we had hypothesized that individuals at-risk for depression may
engage in repetitive music listening behaviors, we defined a repetitiveness
index (RI) per user, computed as shown in Equation 1. In order to capture a
user’s repetitiveness within a session, the proportion of tracks that were
repeated is first calculated. Subsequently, RI is calculated as the average
repetitiveness across all sessions.

$RI_{u}=\frac{1}{N_{u}}\sum_{j\epsilon{N_{u}}}\frac{\sum_{i\epsilon{T_{u,j}}}\left(tr\textsubscript{i,j}\times
I\left(tr\textsubscript{i,j}>=2\right)\right)}{\sum_{i\epsilon{T_{u,j}}}tr\textsubscript{i,j}}$
(1)

where,
$N_{u}$ : number of sessions for user $u$
$T_{u,j}$ : all unique tracks in $jth$ session for user $u$
$tr_{i,j}$ : frequency of track $i$ in $jth$ session
$I(condition)$ : indicator function, 1 if $condition$ evaluates to true, else
0

####  2.2.2 Dynamic Measures Computation

Previous studies have demonstrated the association of dynamic measures such as
variability, instability, and inertia, with depression[27]. Variability
represents the standard deviation of scores across sessions. Inertia is
calculated as the autocorrelation coefficient (with time lag of 1 session) for
the time-varying scores. It captures the predictability of a feature/emotion
from one time-point to the next. Higher inertia and extreme variability have
been found to be representative of ill-being and depressive moods, especially
in negative affect states [21]. Instability is calculated as the mean squared
successive difference (MSSD) for scores across sessions. It measures the
deviation in scores from one time-point to the next. A person with high
instability implies higher fluctuations in music consumption with respect to
the features/emotions. Since, instability has been found to have mathematical
dependency on the other two measures, that is, it is directly proportional to
variability and has inverse relation with inertia [20], we restrict our
analyses to computing only variability and inertia. These two dynamic measures
were calculated for all the session-based acoustic features and QPS.

###  2.3 Statistical Testing

We first performed tests of difference by dividing the users into No-Risk and
At-Risk groups based on their K10 scores as done in Surana et al. [19]. Users
with K10 $<20$ (n=193) fall under the No-Risk group while K10 $>29$ (n=142)
comprised the At-Risk group. We performed a two-tailed Mann Whitney U (MWU)
test on the static summary features between these groups. We further performed
bootstrapping to account for Type I error and ensure that the observed
differences are not due to chance using the same approach as Surana et al.
Next we performed Spearman correlations between K10 and all 541 users’ number
of sessions, total playcount444Here, the total playcount refers to the total
number of tracks(including the repetitions) listened by the user., and RI.
Similarly, correlation between K10 and each of the dynamic measures of audio
and emotion features was computed. We additionally performed permutation
testing to account for multiple comparisons due to the number of correlations
performed and hence account for Type 1 errors. For each correlation,
permutation testing was performed with 10,000 iterations. At each iteration,
the K10 scores were randomly assigned (with replacement) to each user. The
correlation value for each iteration was calculated. The significance of the
original statistic (Spearman correlation) was estimated from the distribution
of the correlation statistics thus obtained.

##  3 Results

There were about 8,09,000 unique tracks in the dataset, out of which the audio
features were available for 5,73,000 ( 71%) tracks on Spotify. No significant
differences were observed between the No-Risk and At-Risk groups using MWU
test based on the static summary features. A borderline significant difference
($p=0.06$) was observed for the acoustic feature speechiness having a higher
median for the At-Risk group. Figure 3 displays the boxplots of the QPS
summary feature for both groups. A borderline group difference ($p=0.1$) for
the QPS in the fourth quadrant (Q4) representing Tenderness. However, we do
observe that the median in the third quadrant (Q3) representing Sadness was
higher for the At-Risk group.

Figure 3: Boxplot of QPS summary feature (for each of the four quadrants) for
No-Risk and At-Risk groups.

On an average, each user had 292 sessions. Significant positive correlations
were observed between K10 and number of sessions ($r=0.16,p=0.0003$), total
playcount ($r=0.11,p=0.01$) and RI ($r=0.16,p=0.0002$). These correlations
were found to be significant post permutation testing (all $p<.01$).

Audio Feature | Variability | Inertia
---|---|---
Danceability | -0.03 | 0.03
Loudness | -0.01 | 0.05
Speechiness | 0.05 | 0.09*
Acousticness | 0.02 | 0.05
Instrumentalness | -0.11** | 0.02
Liveness | -0.05 | 0.05
Tempo | -0.05 | 0.03
Mode | -0.05 | 0.07
Table 1: Spearman correlations between users’ dynamic measures represented by
Variability and Inertia of audio features and K10 scores. (*p<0.05, **p<0.01)

Table 1 displays the correlation results between the dynamic measures of the
audio features and K10 scores. K10 had a negative correlation with variability
in instrumentalness ($r=-0.11,p=0.009$) which retained significance even after
controlling for mean and inertia. Also, K10 correlated positively with inertia
in speechiness ($r=0.09,p=0.03$) retaining significance after controlling for
mean and variability. These correlations were also found to be significant
after permutation testing.

Quadrant | Variability | Inertia
---|---|---
Q1 | -0.06 | 0.03
Q2 | -0.06 | -0.03
Q3 | 0.02 | 0.1*
Q4 | 0.03 | 0.05
Table 2: Spearman correlations between users’ dynamic measures, represented by
Variability and Inertia of QPS and K10 scores. (*p<0.05)

Table 2 presents the correlation results between the dynamic measures of QPS
and K10. As expected, significant positive correlation was observed between
inertia and K10 in the third quadrant (Q3) representing sadness ($p=0.02$)
retaining significance post permutation testing. In addition, this correlation
was preserved after controlling for mean QPS ($r=0.09,p=0.03$).

##  4 Discussion

This study is the first to analyze the association between depression risk and
music consumption via acoustic features. We analyse naturally occurring
listening behavior of individuals on the online music streaming platform
Last.fm as opposed to self-reported or lab-based studies. Further, this study
is the first of its kind to look at the dynamic nature of music consumption to
characterize risk for depression.

No significant differences were found between At-Risk and No-Risk groups in
terms of audio features when they were averaged over the entire listening
history of participants. This suggests that the kinds of music listened by
individuals with varying depression risk has comparable features. However, a
further inquiry into genre preferences might shed light on perceptual
attributes that might be more relevant and representative of At-Risk
individuals’ consumption. The borderline significant difference demonstrated
in the fourth quadrant QPS and sub-threshold observable difference between the
median QPS and respective ranges in Q3 (Figure 3) are very much in line with
previous studies [11, 19]. Individuals with high K10 scores are characterized
by states that are high in anxiety and arousal. When using music as a coping
mechanism, a natural choice may be to listen to music that is low on arousal
owing to their already heightened physiologically aroused states. Since, we
take a subset of the participants to investigate group differences, future
studies can aim to increase sample size to unearth more definitive trends.

Session-based analyses yielded several significant results which are in line
with previous studies. The positive correlation observed between K10 and the
total number of sessions and playcount suggests greater reliance on music for
individuals with higher risk for depression. Higher musical engagement is
representative of emotion focused-coping [28], especially during periods of
depression [7]. Furthermore, the positive association between Repetitiveness
Index and K10 reflects the ruminative coping style which is characteristic of
individuals at-risk for depression [10] which may result in intensifying their
negative moods [11, 29]. Whether this ruminatory behaviour with music as a
virtual other is beneficial or maladaptive in the long-run remains to be seen.

The negative association found between K10 and variability in
instrumentalness, an acoustic feature that indicates the instrumental nature
or lower presence of spoken words in songs, suggests that the greater the risk
of depression, the less the deviation in instrumentalness This result coupled
with higher median instrumentalness for At-Risk group than No-Risk is in line
with the findings of Surana et al. [19] who report that At-Risk individuals
gravitated towards neo-psychedelic-, avant garde-, dream-pop genres that are
characterized by obscure vocals. The positive association between Inertia in
speechiness, an acoustic feature that captures presence of spoken words in a
track, and depression risk suggests that high risk individuals tend to be
resistant to change when listening to certain music associated with specific
levels of speechiness over time. One limitation is the of assignment an
average estimate of an acoustic feature to a track, since it does not capture
within-track variability. Hence, two tracks which sound perceptually different
may have similar values for an acoustic feature as a result of averaging over
the track. However, combining acoustic features with tag information in future
may provide relevant perceptual information and hence better insight into
describing aspects of music associated with individuals at risk.

Finally, the positive association between inertia in the Q3, representing
Sadness in the VA space, and K10 supports our hypothesis that individuals At-
Risk not only listen to music that is more reflective of their negatively
valenced states, but also that this affinity is more resistant to change over
time. Since it is known that individuals at risk for depression exhibit higher
inertia in their own internal states, we can conclude that this behavior is
reflected in their music consumption patterns. This is a novel finding that
further corroborates the notion that music is indeed a mirror of the self,
especially in terms of dynamic states.

In future, we intend to employ a multimodal approach of incorporating tags,
acoustic features, and lyrics-based information such as sentiments, to gain a
holistic understanding of music consumption characterizing depression risk.
This would then pave way to designing early depression detection systems using
digital music footprints.

## References

  * [1] W. H. Organization _et al._ , “Depression and other common mental disorders: global health estimates,” World Health Organization, Tech. Rep., 2017\.
  * [2] T. Vos, C. Allen, M. Arora, R. M. Barber, Z. A. Bhutta, A. Brown, A. Carter, D. C. Casey, F. J. Charlson, A. Z. Chen _et al._ , “Global, regional, and national incidence, prevalence, and years lived with disability for 310 diseases and injuries, 1990–2015: a systematic analysis for the global burden of disease study 2015,” _The lancet_ , vol. 388, no. 10053, pp. 1545–1602, 2016.
  * [3] L. Sher, “The impact of the covid-19 pandemic on suicide rates,” _QJM: An International Journal of Medicine_ , 2020.
  * [4] U. Rehman, M. G. Shahnawaz, N. H. Khan, K. D. Kharshiing, M. Khursheed, K. Gupta, D. Kashyap, and R. Uniyal, “Depression, anxiety and stress among indians in times of covid-19 lockdown,” _Community mental health journal_ , pp. 1–7, 2020.
  * [5] S. Özdin and Ş. Bayrak Özdin, “Levels and predictors of anxiety, depression and health anxiety during covid-19 pandemic in turkish society: The importance of gender,” _International Journal of Social Psychiatry_ , p. 0020764020927051, 2020.
  * [6] C. Mazza, E. Ricci, S. Biondi, M. Colasanti, S. Ferracuti, C. Napoli, and P. Roma, “A nationwide survey of psychological distress among italian people during the covid-19 pandemic: Immediate psychological responses and associated factors,” _International Journal of Environmental Research and Public Health_ , vol. 17, no. 9, p. 3165, 2020.
  * [7] J. Stewart, S. Garrido, C. Hense, and K. McFerran, “Music use for mood regulation: self-awareness and conscious listening choices in young people with tendencies to depression,” _Frontiers in psychology_ , vol. 10, p. 1199, 2019.
  * [8] S. Garrido, T. Eerola, and K. McFerran, “Group rumination: Social interactions around music in people with depression,” _Frontiers in psychology_ , vol. 8, p. 490, 2017.
  * [9] K. S. McFerran, S. Garrido, and S. Saarikallio, “A critical interpretive synthesis of the literature linking music and adolescent mental health,” _Youth & Society_, vol. 48, no. 4, pp. 521–538, 2016.
  * [10] S. Saarikallio, C. Gold, and K. McFerran, “Development and validation of the healthy-unhealthy music scale,” _Child and adolescent mental health_ , vol. 20, no. 4, pp. 210–217, 2015.
  * [11] S. Garrido and E. Schubert, “Music and people with tendencies to depression,” _Music Perception: An Interdisciplinary Journal_ , vol. 32, no. 4, pp. 313–321, 2015.
  * [12] G. Nave, J. Minxha, D. M. Greenberg, M. Kosinski, D. Stillwell, and J. Rentfrow, “Musical preferences predict personality: evidence from active listening and facebook likes,” _Psychological Science_ , vol. 29, no. 7, pp. 1145–1158, 2018.
  * [13] D. M. Greenberg and P. J. Rentfrow, “Music and big data: a new frontier,” _Current opinion in behavioral sciences_ , vol. 18, pp. 50–56, 2017.
  * [14] M. De Choudhury, M. Gamon, S. Counts, and E. Horvitz, “Predicting depression via social media,” in _Seventh international AAAI conference on weblogs and social media_ , 2013.
  * [15] G. Coppersmith, M. Dredze, and C. Harman, “Quantifying mental health signals in twitter,” in _Proceedings of the workshop on computational linguistics and clinical psychology: From linguistic signal to clinical reality_ , 2014, pp. 51–60.
  * [16] M. De Choudhury, S. Counts, E. J. Horvitz, and A. Hoff, “Characterizing and predicting postpartum depression from shared facebook data,” in _Proceedings of the 17th ACM conference on Computer supported cooperative work & social computing_, 2014, pp. 626–638.
  * [17] M. De Choudhury, E. Kiciman, M. Dredze, G. Coppersmith, and M. Kumar, “Discovering shifts to suicidal ideation from mental health content in social media,” in _Proceedings of the 2016 CHI conference on human factors in computing systems_ , 2016, pp. 2098–2110.
  * [18] A. G. Reece and C. M. Danforth, “Instagram photos reveal predictive markers of depression,” _EPJ Data Science_ , vol. 6, no. 1, pp. 1–12, 2017.
  * [19] A. Surana, Y. Goyal, M. Shrivastava, S. Saarikallio, and V. Alluri, “Tag2risk: Harnessing social music tags for characterizing depression risk,” in _To appear in proceedings of the 21st International Society for Music Information Retrieval Conference_ , 2020.
  * [20] P. Koval, M. L. Pe, K. Meers, and P. Kuppens, “Affect dynamics in relation to depressive symptoms: variable, unstable or inert?” _Emotion_ , vol. 13, no. 6, p. 1132, 2013.
  * [21] P. Kuppens and P. Verduyn, “Emotion dynamics,” _Current Opinion in Psychology_ , vol. 17, pp. 22–26, 2017.
  * [22] M. Houben, W. Van Den Noortgate, and P. Kuppens, “The relation between short-term emotion dynamics and psychological well-being: A meta-analysis.” _Psychological bulletin_ , vol. 141, no. 4, p. 901, 2015.
  * [23] R. C. Kessler, G. Andrews, L. J. Colpe, E. Hiripi, D. K. Mroczek, S.-L. Normand, E. E. Walters, and A. M. Zaslavsky, “Short screening scales to monitor population prevalences and trends in non-specific psychological distress,” _Psychological medicine_ , vol. 32, no. 6, pp. 959–976, 2002\.
  * [24] J. A. Russell, “A circumplex model of affect.” _Journal of personality and social psychology_ , vol. 39, no. 6, p. 1161, 1980.
  * [25] K. Gupta, N. Sachdeva, and V. Pudi, “Explicit modelling of the implicit short term user preferences for music recommendation,” in _European Conference on Information Retrieval_. Springer, 2018, pp. 333–344.
  * [26] J. Rottenberg, “Mood and emotion in major depression,” _Current Directions in Psychological Science_ , vol. 14, no. 3, pp. 167–170, 2005.
  * [27] E. M. Seabrook, M. L. Kern, B. D. Fulcher, and N. S. Rickard, “Predicting depression from language-based emotion dynamics: longitudinal analysis of facebook and twitter status updates,” _Journal of medical Internet research_ , vol. 20, no. 5, p. e168, 2018.
  * [28] D. Miranda, P. Gaudreau, R. Debrosse, J. Morizot, and L. J. Kirmayer, “Music listening and mental health: Variations on internalizing psychopathology,” _Music, health, and wellbeing_ , pp. 513–529, 2012.
  * [29] S. Garrido and E. Schubert, “Moody melodies: Do they cheer us up? a study of the effect of sad music on mood,” _Psychology of Music_ , vol. 43, no. 2, pp. 244–261, 2015.


$\displaystyle=(\overline{\ell}(\theta,\mathbf{z})-\overline{\ell}(\theta^{\prime},\mathbf{z}))\cdot\mathbb{I}\left[\overline{k}_{\overline{\phi}}(\theta_{\mathrm{d}},\mathbf{z})=\overline{k}_{\overline{\phi}}(\theta_{\mathrm{d}}^{\prime},\mathbf{z})\right]+(\overline{\ell}(\theta,\mathbf{z})-\overline{\ell}(\theta^{\prime},\mathbf{z}))\cdot\mathbb{I}\left[\overline{k}_{\overline{\phi}}(\theta_{\mathrm{d}},\mathbf{z})\neq\overline{k}_{\overline{\phi}}(\theta_{\mathrm{d}}^{\prime},\mathbf{z})\right]$
(F.34) $\displaystyle\leq
2\cdot\mathbb{I}\left[\overline{k}_{\overline{\phi}}(\theta_{\mathrm{d}},\mathbf{z})\neq\overline{k}_{\overline{\phi}}(\theta_{\mathrm{d}}^{\prime},\mathbf{z})\right]+\max_{k\in[K]}g_{k}(\theta_{\mathrm{c}},\mathbf{z})-g_{k}(\theta_{\mathrm{c}}^{\prime},\mathbf{z})$
(F.35) $\displaystyle\leq
2\cdot\mathbb{I}\left[\overline{k}_{\overline{\phi}}(\theta_{\mathrm{d}},\mathbf{z})\neq\overline{k}_{\overline{\phi}}(\theta_{\mathrm{d}}^{\prime},\mathbf{z})\right]+\max_{k\in[K]}\left|\left|\theta_{\mathrm{c}}^{(k)}-\theta_{\mathrm{c}}^{{}^{\prime}(k)}\right|\right|_{1}.$
(F.36)

The result then follows by the definition of $\rho$.

###  F.3 Replacing $\overline{\ell}$ with $\ell$

While the work in Section F.1 sufficed to prove Theorem 2, for the sake of
planning, we may wish to replace the loss function $\overline{\ell}$ with the
much simpler $\ell$ of (4.2). In order to apply our techniques, however, we
will require that $\theta_{\mathrm{d}}=(\mathbf{w}_{1},\dots,\mathbf{w}_{K})$
satisfies a certain margin condition. The analogue of Section F.1 is thus:

######  Theorem 6.

Suppose that $\mathcal{Z}\subset\mathbb{R}^{d}$ and $\Theta$ is a subset of a
Euclidean space of $\ell_{1}$ diameter bounded by $D$, and that

$\displaystyle\Theta_{\mathrm{d}}\subset\left\\{(\mathbf{w}_{1},\dots,\mathbf{w}_{K})\in(\mathcal{S}^{d})^{\times
K}|\min_{k\neq
k^{\prime}\in[K]}\left|\left|\mathbf{w}_{k,\widehat{d}}-\mathbf{w}_{k^{\prime},\widehat{d}}\right|\right|_{2}\geq\gamma\right\\},$
(F.37)

where we denote by $\mathbf{w}_{k}$ the coordinates of a given
$\theta_{\mathrm{d}}\in\Theta_{\mathrm{d}}$ and let
$\mathbf{w}_{k,\widehat{d}}$ denote the first $d$ coordinates of
$\mathbf{w}_{k}$. Suppose further that
$\phi(\theta_{\mathrm{d}},k,\mathbf{z})=\psi(\left\langle\mathbf{w}_{k},(\mathbf{z},1)\right\rangle)$
for some link function $\psi$, as in Theorem 2. If $\mathcal{M}$ consists of
the class of $\sigma_{\mathrm{dir}}$-directionally smooth distributions such
that $\left|\left|\mathbf{z}\right|\right|_{\infty}\leq B$ almost surely for
some $B\geq 1$, then with $\rho$ as in (4.6), it holds that $\rho$ is a
pseudo-metric satisfying the pseudo-isometry property with
$\alpha=\frac{4AB}{a\gamma\sigma_{\mathrm{dir}}}$ and $\beta=1$. Furthermore,
for all $\epsilon>0$,

$\displaystyle\mathcal{N}_{\mathcal{M},[]}\left(\Theta,\rho,\epsilon\right)\leq\left(\frac{18AK^{2}BD}{a\gamma\sigma_{\mathrm{dir}}\epsilon}\right)^{2K(d+1)}$
(F.38)

###### Proof.

The proof is essentially the same as that of Theorem 2 given in Section F.1.
In fact, we simply need to prove a version of Lemma F.1 and the rest of the
proof applies, _mutatis mutandis_. To see this, note that we may mimic the
aforementioned proof by setting
$\mathbf{w}_{kk^{\prime}}=\mathbf{w}_{k}-\mathbf{w}_{k^{\prime}}$; this is
almost the same as the previous scenario with the exception that we may now
take $\left|\left|\mathbf{w}_{kk^{\prime}}\right|\right|\neq 1$. This causes a
problem only in the application of directional smoothness; thus, suppose that
$\mathbf{z}$ is $\sigma_{\mathrm{dir}}$ directionally smooth and observe that
the chain of inequalities in (F.5) remains valid. Continuing, we see that for
fixed $k,k^{\prime}\in[K]$,

$\displaystyle\mathbb{P}$
$\displaystyle\left(\psi(\left\langle\mathbf{w}_{kk^{\prime}},(\mathbf{z},1)\right\rangle)\geq
0>\psi(\left\langle\mathbf{w}_{kk^{\prime}}^{\prime},(\mathbf{z},1)\right\rangle)\right)$
(F.39)
$\displaystyle\leq\mathbb{P}\left(\psi(\left\langle\mathbf{w}_{kk^{\prime}},(\mathbf{z},1)\right\rangle)\leq\left|\psi(\left\langle\mathbf{w}_{kk^{\prime}},(\mathbf{z},1)\right\rangle)-\psi(\left\langle\mathbf{w}_{kk^{\prime}}^{\prime},(\mathbf{z},1)\right\rangle)\right|\right)$
(F.40)
$\displaystyle\leq\mathbb{P}\left(\psi(\left|\left\langle\mathbf{w}_{kk^{\prime}},(\mathbf{z},1)\right\rangle\right|)\leq
A\left|\left\langle\mathbf{w}_{kk^{\prime}}-\mathbf{w}_{kk^{\prime}}^{\prime},(\mathbf{z},1)\right\rangle\right|\right)$
(F.41)
$\displaystyle\leq\mathbb{P}\left(\psi(\left|\left\langle\mathbf{w}_{kk^{\prime}},(\mathbf{z},1)\right\rangle\right|)\leq
AB\left|\left|\mathbf{w}_{kk^{\prime}}-\mathbf{w}_{kk^{\prime}}^{\prime}\right|\right|_{1}\right)$
(F.42)
$\displaystyle\leq\mathbb{P}\left(\psi(\left|\left\langle\mathbf{w}_{k}-\mathbf{w}_{k^{\prime}},(\mathbf{z},1)\right\rangle\right|)\leq
AB(\left|\left|\mathbf{w}_{k}-\mathbf{w}_{k}^{\prime}\right|\right|_{1}+\left|\left|\mathbf{w}_{k^{\prime}}-\mathbf{w}_{k^{\prime}}^{\prime}\right|\right|_{1})\right)$
(F.43)
$\displaystyle\leq\frac{AB}{a\sigma_{\mathrm{dir}}\cdot\left|\left|\mathbf{w}_{k,\widehat{d}}-\mathbf{w}_{k^{\prime},\widehat{d}}\right|\right|_{2}}\cdot\left(\left|\left|\mathbf{w}_{k}-\mathbf{w}_{k}^{\prime}\right|\right|_{1}+\left|\left|\mathbf{w}_{k^{\prime}}-\mathbf{w}_{k^{\prime}}^{\prime}\right|\right|_{1}\right)$
(F.44)
$\displaystyle\leq\frac{AB}{a\sigma_{\mathrm{dir}}\gamma}\cdot\left(\left|\left|\mathbf{w}_{k}-\mathbf{w}_{k}^{\prime}\right|\right|_{1}+\left|\left|\mathbf{w}_{k^{\prime}}-\mathbf{w}_{k^{\prime}}^{\prime}\right|\right|_{1}\right),$
(F.45)

where the first four inequalities follow as in (F.10), the fifth inequality
follows from the definition of $\mathbf{w}_{kk^{\prime}}$, the penultimate
inequality follows as in the previous proof, and the last inequality follows
from the margin assumption. We then may apply the identical logic as in the
proof of Theorem 2 going forward and the result holds, after channging the
dimension of $\Theta_{\mathrm{d}}$ and adding a multiplicative factor of 2 to
account for summing twice the differences
$\left|\left|\mathbf{w}_{k}-\mathbf{w}_{k}^{\prime}\right|\right|_{1}$ above.
∎

Using the identical argument as in Corollary 4.1, we arrive at the following
regret bound for Algorithm 2 in the situation of Theorem 6:

######  Corollary F.1.

Suppose that $\ell$ is as in (4.2) with $\phi$ and $\Theta$ as in Theorem 6
with $B\geq 1$ and $\ell$ uniformly bounded in magnitude by $1$. If we set
$\eta=\operatorname{\widetilde{\mathcal{O}}}\left({\left(TKAdDB(\gamma
a\sigma_{\mathrm{dir}})^{-1}\right)^{2/3}}\right)$ and $n=\sqrt{\eta}$, then
Algorithm 2 expereinces

$\displaystyle\mathbb{E}\left[\operatorname{Reg}_{T}\right]\leq\operatorname{\widetilde{\mathcal{O}}}\left({\left(\frac{TAKdBD}{a\gamma\sigma_{\mathrm{dir}}}\right)^{2/3}}\right).$
(F.46)

In particular, the oracle complexity of achieving average regret $\epsilon$ is
$\operatorname{\widetilde{\mathcal{O}}}\left({\frac{AKdDB}{\gamma
a\sigma_{\mathrm{dir}}\epsilon^{2}}}\right)$.

##  Appendix G Proofs from Section 4.3

In this appendix, we discuss the polynomially smooth assumption and provide
examples of common distributions satisfying this requirement. We also give a
counter example that demonstrates that directional smoothness is _not_
sufficient to ensure polynomial smoothness. We then prove Theorem 3.

###  G.1 Polynomial Smoothness

In this section, we discuss the notion of Polynomial smoothness found in
Definition 4.1. We begin by recalling the simple Glazer and Mikulincer [2022,
Example 3], which demonstrates that $\sigma_{\mathrm{dir}}$-smoothness is
strictly weaker than polynomial smoothness:

######  Example G.1.

We show that there exists a class of distributions that is
$\sigma_{\mathrm{dir}}$-directionally smooth with $\sigma_{\mathrm{dir}}$
decaying polynomially with dimension, but is
$\sigma_{\mathrm{poly},2}$-polynomially smooth only for
$\sigma_{\mathrm{poly},2}$ decaying exponentially with dimension. Let
$\nu_{d}$ denote the uniform measure on the unit Euclidean ball
$\mathcal{B}^{d}\subset\mathbb{R}^{d}$. We observe that by Block and
Simchowitz [2022, Example 1], $\nu_{d}$ is
$\sigma_{\mathrm{dir}}$-directionally smooth with
$\sigma_{\mathrm{dir}}=\operatorname{\Omega}\left({\frac{1}{d}}\right)$. On
the other hand, for the polynomial
$f(x)=\frac{1}{d}\cdot\left|\left|x\right|\right|_{2}^{2}$, we see that
$\mathrm{coeff}_{2}(f)=1$, but concentration of measure (see Vershynin [2018]
for example) tells us that
$\mathbb{P}\left(\left|f(x)-1\right|\leq\epsilon\right)\geq
1-e^{-\Omega(d)\epsilon}$.

We now consider what kinds of distributions are polynomially smooth. The key
tool in our arsenal is (a special case of ) the famous inequality of Carbery-
Wright, which says:

######  Theorem 7 (Theorem 8 from Carbery and Wright [2001]).

If $\nu$ is a log-concave measure on $\mathbb{R}^{d}$ and
$f:\mathbb{R}^{d}\to\mathbb{R}$ is a degree $r$ polynomial, then for all
$\epsilon>0$, if $X\sim\nu$,

$\displaystyle\mathbb{P}\left(\left|f(X)\right|\leq\epsilon\right)\leq
Cr\frac{\epsilon^{\frac{1}{r}}}{\mathbb{E}\left[f(X)^{2}\right]^{\frac{1}{2r}}}.$
(G.1)

Thus, Theorem 7 tells us that if $\nu$ is log-concave and we can be assured
that all polynomials $f$ with $\mathrm{coeff}_{r}(f)\geq 1$ have large second
moment, then $\nu$ is $\sigma_{\mathrm{poly},r}$-polynomially smooth with
$\sigma_{\mathrm{poly},r}$ depending nicely on the dimension. Proving that
polynomials with large coefficients indeed have large second moment is still
an active area of research, but we provide as an example the following result,
rephrased into our language:

######  Theorem 8 (Corollary 4 from Glazer and Mikulincer [2022]).

Suppose that $\nu=\mu^{\otimes n}$ is a log-concave, isotropic product
measure. Then $\nu$ is $\sigma_{\mathrm{poly},r}$-polynomially smooth with
$\sigma_{\mathrm{poly},r}\geq\operatorname{\Omega}\left({\frac{1}{r}}\right)$.

Note that the above result encompasses Gaussian measures and can be scaled as
needed. Further results in the direction of Glazer and Mikulincer [2022] would
translate directly into a wider class of measures known to be
$\sigma_{\mathrm{poly},r}$-polynomially smooth.

###  G.2 Proof of Theorem 3

In this section, we provide a proof of Theorem 3 that follows the approach of
Corollary 4.1. While we do not repeat the argument, we observe in passing that
replacing the tournament-style $\overline{\ell}$ with the simpler function
$\ell$ from (4.2) and including a margin assumption allows for an analogue of
Theorem 6 in this setting. To prove Theorem 3, we begin by proving an analogue
of Theorem 2:

######  Theorem 9.

Suppose that $\mathcal{Z}\subset\mathbb{R}^{d}$ and that $\Theta$ is a subset
of Euclidean space with $\ell_{1}$ diameter bounded by $D$. Let
$\Theta_{\mathrm{d}}$ parameterize the set of tuples of $\binom{K}{2}$ degree
$r$ polynomials $(f_{\mathbf{w}_{kk^{\prime}}})$ on $\mathbb{R}^{d}$ such that
$\mathrm{coeff}_{r}(f_{\mathbf{w}_{kk^{\prime}}})=1$ for all $k\in[K]$. If
$\overline{\phi}(\theta_{\mathrm{d}},k,k^{\prime},\mathbf{z})=f_{\mathbf{w}_{kk^{\prime}}}(\mathbf{z})$
and $\mathcal{M}$ is the class of $\sigma_{\mathrm{poly},r}$-polynomially
smooth distributions such that
$\left|\left|\mathbf{z}\right|\right|_{\infty}\leq B$ almost surely, then the
$\rho$ defined in (4.6) is a pseudo-metric satisfying the pseudo-isometry
property with $\alpha=\frac{2B^{r}D}{\sigma_{\mathrm{poly},r}}$ and
$\beta=\frac{1}{r}$. Furthermore, for all $\epsilon>0$,

$\displaystyle\mathcal{N}_{\mathcal{M},[]}(\Theta,\rho,\epsilon)\leq\left(\frac{9K^{2}B}{\sigma_{\mathrm{poly},r}\epsilon}\right)^{K^{2}r^{2}d^{r}}.$
(G.2)

To prove the result, we need analogues of Lemmas F.1,F.2, and F.3. We begin
with proving the Lipschitzness in expectation of the first term of $\rho$:

######  Lemma G.1.

Suppose that $\Theta_{\mathrm{d}}$, $\overline{\phi}$, and
$\overline{k}_{\overline{\phi}}$ are as in Theorem 9 and suppose that
$\mathbf{z}$ is chosen from a $\sigma_{\mathrm{poly},r}$-polynomially smooth
distribution such that $\left|\left|\mathbf{z}\right|\right|_{\infty}\leq B$
almost surely for some $B\geq 1$. Then,

$\displaystyle\mathbb{P}\left(\overline{k}_{\overline{\phi}}(\theta_{\mathrm{d}},\mathbf{z})\neq\overline{k}_{\overline{\phi}}(\theta_{\mathrm{d}}^{\prime},\mathbf{z})\right)\leq\frac{B^{r}K^{2-\frac{4}{r}}}{\sigma_{\mathrm{poly},r}}\cdot\left|\left|\theta_{\mathrm{d}}-\theta_{\mathrm{d}}^{\prime}\right|\right|_{1}^{\frac{1}{r}}.$
(G.3)

###### Proof.

By the same argument as in (F.5), we have that

$\displaystyle\mathbb{P}\left(\overline{k}_{\overline{\phi}}(\theta_{\mathrm{d}},\mathbf{z})\neq\overline{k}_{\overline{\phi}}(\theta_{\mathrm{d}}^{\prime},\mathbf{z})\right)$
$\displaystyle\leq\sum_{k,k^{\prime}\in[K]}\mathbb{P}\left(f_{\mathbf{w}_{kk^{\prime}}}(\mathbf{z})\geq
0>f_{\mathbf{w}_{kk^{\prime}}^{\prime}}(\mathbf{z})\right).$ (G.4)

Observe that by the triangle inequality,

$\displaystyle\left|f_{\mathbf{w}_{kk^{\prime}}}(\mathbf{z})-f_{\mathbf{w}_{kk^{\prime}}^{\prime}}(\mathbf{z})\right|\leq
B^{r}\cdot\left|\left|\mathbf{w}_{kk^{\prime}}-\mathbf{w}_{kk^{\prime}}^{\prime}\right|\right|_{1}.$
(G.5)

Thus, applying the argument in (F.10), we have

$\displaystyle\mathbb{P}\left(f_{\mathbf{w}_{kk^{\prime}}}(\mathbf{z})\geq
0>f_{\mathbf{w}_{kk^{\prime}}^{\prime}}(\mathbf{z})\right)$
$\displaystyle\leq\mathbb{P}\left(\left|f_{\mathbf{w}_{kk^{\prime}}}(\mathbf{z})\right|\leq\left|\left|f_{\mathbf{w}_{kk^{\prime}}}(\mathbf{z})-f_{\mathbf{w}_{kk^{\prime}}^{\prime}}(\mathbf{z})\right|\right|\right)$
(G.6)
$\displaystyle\leq\mathbb{P}\left(\left|f_{\mathbf{w}_{kk^{\prime}}}(\mathbf{z})\right|\leq
B^{r}\cdot\left|\left|\mathbf{w}_{kk^{\prime}}-\mathbf{w}_{kk^{\prime}}^{\prime}\right|\right|_{1}\right)$
(G.7)
$\displaystyle\leq\frac{B}{\sigma_{\mathrm{poly},r}}\cdot\left|\left|\mathbf{w}_{kk^{\prime}}-\mathbf{w}_{kk^{\prime}}^{\prime}\right|\right|_{1}^{\frac{1}{r}},$
(G.8)

where the last inequality follows from the definition of polynomial
smoothness. Applying Hölder’s inequality and summing concludes the proof. ∎

Using this result, we can prove an analogue of Lemma F.2:

######  Lemma G.2.

Suppose that we are in the situation of Theorem 9 and $\mathcal{M}$ is the
class of $\sigma_{\mathrm{poly},r}$-polynomially smooth distributions such
that the infinity norms of samples are uniformly bounded almost surely by some
$B\geq 1$. If the $\ell_{1}$ diameter of $\Theta$ is bounded by $D$, then

$\displaystyle\sup_{\nu\in\mathcal{M}}\mathbb{E}_{\nu}\left[\rho(\theta,\theta^{\prime},\mathbf{z})\right]\leq\frac{2BD}{\sigma_{\mathrm{poly},r}}\cdot\left|\left|\theta-\theta^{\prime}\right|\right|^{\frac{1}{r}}.$
(G.9)

###### Proof.

We compute:

$\displaystyle\mathbb{E}_{\nu}\left[\rho(\theta,\theta^{\prime},\mathbf{z})\right]$
$\displaystyle=\mathbb{E}_{\nu}\left[2\cdot\mathbb{I}\left[\overline{k}_{\overline{\phi}}(\theta_{\mathrm{d}},\mathbf{z})\neq\overline{k}_{\overline{\phi}}(\theta_{\mathrm{d}}^{\prime},\mathbf{z})\right]+\max_{k\in[K]}\left|\left|\theta_{\mathrm{c}}^{(k)}-\theta_{\mathrm{c}}^{{}^{\prime}(k)}\right|\right|_{1}\right]$
(G.10)
$\displaystyle\leq\frac{2B}{\sigma_{\mathrm{poly},r}}\cdot\left|\left|\theta_{\mathrm{d}}-\theta_{\mathrm{d}}^{\prime}\right|\right|_{1}^{\frac{1}{r}}+\left|\left|\theta_{\mathrm{c}}-\theta_{\mathrm{c}}^{\prime}\right|\right|_{1}$
(G.11)
$\displaystyle\leq\frac{2BD}{\sigma_{\mathrm{poly},r}}\cdot\left|\left|\theta-\theta^{\prime}\right|\right|^{\frac{1}{r}},$
(G.12)

where the second inequality follows from Lemma G.1 and the last inequality
follows by the assumption on the diameter. ∎

Finally, we require an analogue of Lemma F.3:

######  Lemma G.3.

If we are in the situation of Theorem 9 then for any $\epsilon>0$, it holds
that

$\displaystyle\mathcal{N}_{\mathcal{M},[]}(\Theta,\rho,\epsilon)\leq\left(\frac{9K^{2}B}{\sigma_{\mathrm{poly},r}\epsilon}\right)^{K^{2}r^{2}d^{r}}.$
(G.13)

###### Proof.

We mimic the proof of Lemma F.3 but apply Lemma G.1 instead of Lemma F.1. In
particular, we suppose that
$\mathcal{N}=\left\\{\theta_{i}=\left(\theta_{\mathrm{c}}^{i},\theta_{\mathrm{d}}^{i}\right)\right\\}$
is an $\widetilde{\epsilon}$-net of $\Theta$ with respect to $\ell_{1}$, where
$\widetilde{\epsilon}=\left(\frac{\sigma_{\mathrm{poly},r}}{3K^{2}B}\cdot\epsilon\right)^{r}$
and similarly let $\mathcal{B}_{i}\subset\Theta$ denote the set of parameters
within $\widetilde{\epsilon}$ of $\theta_{i}$ in $\ell_{1}$ norm. We compute
as in the proof of Lemma F.3 that

$\displaystyle\mathbb{P}\left(\exists\theta\in\mathcal{B}_{i}\text{ s.t.
}\overline{k}_{\overline{\phi}}(\theta_{\mathrm{d}},\mathbf{z})\neq\overline{k}_{\overline{\phi}}(\theta_{\mathrm{d}}^{i},\mathbf{z})\right)$
$\displaystyle\leq\mathbb{P}\left(\exists\theta\in\mathcal{B}_{i}\text{ s.t.
}\left|f_{\mathbf{w}_{kk^{\prime}}^{i}}(\mathbf{z})\right|\leq\left|f_{\mathbf{w}_{kk^{\prime}}}(\mathbf{z})-f_{\mathbf{w}_{kk^{\prime}}^{i}}(\mathbf{z})\right|\right)$
(G.14) $\displaystyle\leq\mathbb{P}\left(\exists\theta\in\mathcal{B}_{i}\text{
s.t. }\left|f_{\mathbf{w}_{kk^{\prime}}^{i}}(\mathbf{z})\right|\leq
B^{r}\cdot\left|\left|\mathbf{w}_{kk^{\prime}}-\mathbf{w}_{kk^{\prime}}^{i}\right|\right|_{1}\right)$
(G.15) $\displaystyle\leq\mathbb{P}\left(\exists\theta\in\mathcal{B}_{i}\text{
s.t. }\left|f_{\mathbf{w}_{kk^{\prime}}^{i}}(\mathbf{z})\right|\leq
B^{r}\cdot\widetilde{\epsilon}\right)$ (G.16)
$\displaystyle\leq\frac{K^{2}B}{\sigma_{\mathrm{poly},r}}\cdot\widetilde{\epsilon}^{\frac{1}{r}}.$
(G.17)

Thus

$\displaystyle\sup_{\nu\in\mathcal{M}}\mathbb{E}_{\nu}\left[\rho(\theta,\theta_{i},\mathbf{z})\right]$
$\displaystyle\leq
2\cdot\sup_{\nu\in\mathcal{M}}\left\\{\mathbb{E}_{\nu}\left[\sup_{\theta\in\mathcal{B}_{i}}\mathbb{I}\left[\overline{k}_{\overline{\phi}}(\theta_{\mathrm{d}},\mathbf{z})\neq\overline{k}_{\overline{\phi}}(\theta_{\mathrm{d}}^{i},\mathbf{z})\right]\right]\right\\}+\sup_{\theta\in\mathcal{B}_{i}}\left|\left|\theta_{\mathrm{c}}-\theta_{\mathrm{c}}^{i}\right|\right|_{1}$
(G.18)
$\displaystyle\leq\frac{2K^{2}B}{\sigma_{\mathrm{poly},r}}\cdot\widetilde{\epsilon}^{\frac{1}{r}}+\widetilde{\epsilon}$
(G.19)
$\displaystyle\leq\frac{3K^{2}B}{\sigma_{\mathrm{poly},r}}\cdot\widetilde{\epsilon}^{\frac{1}{r}}$
(G.20) $\displaystyle\leq\epsilon.$ (G.21)

Thus $\mathcal{N}$ is a generalized $\epsilon$-bracket with respect to
$\mathcal{M}$ and $\rho$. We may bound the size of $\mathcal{N}$ in the same
way as in the proof of Lemma F.3, after observing that
$\mathbf{w}_{kk^{\prime}}$ lives in a space of dimension

$\displaystyle\sum_{i\leq r}\binom{d}{i}\leq\left(\frac{ed}{r}\right)^{r}.$
(G.22)

∎

Combining Lemmas G.2 and G.3 concludes the proof of Theorem 9. We are now
ready to prove Theorem 3:

###### Proof of Theorem 3.

We observe by the same logic as in the proof of Corollary 4.1 that
$\overline{\ell}$ is Lipschitz with respect to $\rho$. Thus we may apply
Theorem 1 and Theorem 9 to get that if Algorithm 2 is played, then

$\displaystyle\mathbb{E}\left[\operatorname{Reg}_{T}\right]\leq\operatorname{\widetilde{\mathcal{O}}}\left({\eta+\frac{T}{n}K^{2}r^{2}d^{r}\log\left(\frac{1}{\sigma_{\mathrm{poly},r}}\right)+\frac{TB^{r}D}{\sigma_{\mathrm{poly},r}}\cdot\left(\frac{K^{2}r^{2}d^{r}}{\eta}\right)^{\frac{1}{4r-2}}}\right).$
(G.23)

Setting

$\displaystyle\eta=\widetilde{\operatorname{\Theta}}\left({\left(\frac{TK^{2}r^{2}d^{r}DB}{\sigma_{\mathrm{poly},r}}\right)^{\frac{4r-2}{4r-1}}}\right)$
$\displaystyle
n=\widetilde{\operatorname{\Theta}}\left({\left(\frac{TK^{2}r^{2}d^{r}DB}{\sigma_{\mathrm{poly},r}}\right)^{\frac{2r-1}{4r-1}}}\right)$
(G.24)

concludes the proof. ∎

##  Appendix H Proof of Theorem 4

In this section, we state and prove a formal version of Theorem 4. We recall
that we are in the situation of (5.1) and that our aim is to minimize the
regret with respect to the best plan $\bar{\mathbf{u}}_{1:H}$. Throughout, we
let $\|\cdot\|_{1}$ denote the $\ell_{1}$ norm interpreted in the natural
sense for concatenated vectors; e.g.
$\|\bar{\mathbf{u}}_{1:H}\|_{1}=\sum_{h=1}^{H}\|\mathbf{u}_{h}\|_{1}$. We
begin by introducing a notation that will substantially simplify our
presentation:

######  Definition H.1.

For a given sequence of modes $k_{1:H}\in[K]^{H}$, recall from (5.1) that the
states evolve as

$\displaystyle\tilde{}\mathbf{x}_{t,h+1}(\theta;k_{1:H})=g_{t,h,k_{h}}(\tilde{}\mathbf{x}_{t,h}(\theta;k_{1:H}),\mathbf{u}_{t,h}(\theta))+\bm{\eta}_{t,h},~{}~{}\tilde{}\mathbf{x}_{t,1}(\theta;k_{1:H})=\mathbf{x}_{t,1},~{}~{}\mathbf{u}_{t,h}(\theta)=\bar{\mathbf{u}}_{h}+\bm{\xi}_{t,h},$
(H.1)

where the difference between here and the situation in (5.1) is that here the
mode sequence is given, whereas in (5.1) it was state and input dependent. We
define the function

$\displaystyle
G_{t}(\theta;k_{1:H}):=\left(\tilde{}\mathbf{x}_{t,1}(\theta;k_{1:H}),\dots,\tilde{}\mathbf{x}_{t,H}(\theta;k_{1:H})\right)\in\mathcal{X}^{H}\subset\mathbb{R}^{mH},$
(H.2)

which maps a plan and given mode sequence to the associated trajectory.

We are now ready to state a formal version of Theorem 4:

######  Theorem 10.

For fixed planning horizon $H$, suppose that trajectories $\mathbf{x}_{t,1:H}$
evolve as in (5.1), where the learner chooses a plan
$\theta\in\mathcal{K}\subset\mathcal{U}^{\times H}$ at each time $t$ and the
adversary presents the tuple $\mathbf{z}_{t}$ described in Section 5. Assume
that for all $t\in[T]$ the following properties hold almost surely under the
adversary’s strategy $p_{t}$:

  1. 1.

$\mathbf{x}_{t,1}\mid\mathcal{F}_{t}$ and
$(\bm{\eta}_{t,h},\bm{\xi}_{t,h})\mid\mathcal{F}_{t,h-1}$ are
$\sigma_{\mathrm{dir}}$-directionally smooth.

  2. 2.

For all mode sequences $k_{1:H}\in[K]^{H}$ and
$\theta,\theta^{\prime}\in\mathcal{U}^{\times H}$,
$\left|\left|G_{t}(\theta,k_{1:H})-G_{t}(\theta^{\prime},k_{1:H})\right|\right|\leq
L\left|\left|\theta-\theta^{\prime}\right|\right|_{1}$, i.e., the functions
$G_{t}$ are $L$-Lipschitz with respect to the $\ell_{1}$ norm.

  3. 3.

For all $h\in[H]$,
$\sup_{\theta\in\mathcal{K}}\left|\left|\mathbf{u}_{t,h}(\theta)\right|\right|_{1}\vee\left|\left|\mathbf{x}_{t,h}(\theta)\right|\right|_{1}\leq
D$.

  4. 4.

For some $\gamma>0$, it holds for all $h\in[H]$ that $\min_{k\neq
k^{\prime}}\left|\left|\mathbf{w}_{t,h,k,\widehat{d}}-\mathbf{w}_{t,h,k^{\prime},\widehat{d}}\right|\right|_{2}\geq\gamma$,
where we let $\mathbf{w}_{\widehat{d}}$ denote the first $d$ coordinates of
the vector $\mathbf{w}\in\mathbb{R}^{d+1}$.

  5. 5.

For all $\mathbf{v}_{1:H},\mathbf{v}_{1:H}^{\prime}\in\mathcal{V}^{H}$ with
$\|\mathbf{v}_{1:H}\|_{1}\vee\|\mathbf{v}_{1:H}^{\prime}\|_{1}\leq 2D$, we
have that the loss functions $\ell^{v}_{t}$ are Lipschitz with respect to the
$\ell_{1}$ norm and bounded, i.e.,
$|\ell^{v}_{t}(\mathbf{v}_{1:H})-\ell^{v}_{t}(\mathbf{v}_{1:H}^{\prime})|\leq\|\mathbf{v}_{1:H}-\mathbf{v}_{1:H}\|_{1}$
and $|\ell^{v}_{t}(\mathbf{v}_{1:H})|\leq 1$.

If the planner plays $\theta_{t}$ according to Algorithm 2 with
$\eta=d^{1/3}H^{5/3}K^{4/3}\left(\frac{TLD}{\gamma\sigma_{\mathrm{dir}}}\right)^{2/3}$
and $n=\sqrt{\eta}$, then

$\displaystyle\mathbb{E}\left[\operatorname{Reg}_{T}\right]\leq\operatorname{\widetilde{\mathcal{O}}}\left({d^{1/3}H^{5/3}K^{4/3}\left(\frac{TLd}{\gamma\sigma_{\mathrm{dir}}}\right)^{2/3}}\right).$
(H.3)

Thus the oracle complexity of achieving average regret $\epsilon$ is
$\operatorname{\widetilde{\mathcal{O}}}\left({d^{1/3}D^{2/3}H^{5/3}K^{4/3}L^{2/3}(\gamma\sigma_{\mathrm{dir}})^{-2/3}\epsilon^{-2}}\right)$.

######  Remark H.1 (Scaling of $L$ and $D$).

Notice that the scaling of the parameters $L$ and $D$ depend on the $H$-fold
compositions of the dynamic maps $g_{t,k,h}$. Thus in the second assumption in
the above theorem, requiring that the maps $G_{t}$ are $L$-Lipschitz, can
naïvely allow $L$ to scale like $\mathrm{poly}(H)\cdot(\Lambda)^{H}$ in the
worst case when we only assume that the functions $g_{t,k,h}$ are
$\Lambda$-Lipschitz. Similarly, if we only suppose that
$g_{t,k,h}(\mathbf{v})\leq c_{2}\|\mathbf{v}\|+c_{1}$, the bound $D$ in the
third and last assumption above could scale with $(c_{2})^{H}$. While these
bounds are tight in general, the exponential dependencies can be mitigated
with common stability assumptions, often imposed in control settings. For
example, under incremental stability of the composed dynamics [Pfrommer et
al., 2022, Angeli, 2000], $L$ would scale only polynomially in $H$. Further
notions of input-to-state stability such as those found in Jadbabaie and
Hauser [2001] result in polynomially-bounded $D$. Thus in many practical
settings of interest, the parameters $L,D$ scale only polynomially in all of
the relevant problem parameters. Note that in the popular Linear Quadratic
Regulator framework, of which our setting is a vast generalization, these
stability assumptions are standard [Hazan and Singh, 2022].

As in the previous applications of Theorem 1, we will prove an analogue of
Theorem 2 where we introduce a pseudo-metric $\rho$ and prove that it
satisfies pseudo-isometry and provides control of the generalized bracketing
numbers. We will then conclude by proving that our $\ell$ is Lipschitz with
respect to $\rho$ and appealing to Theorem 1. For the sake of simplicity, we
will drop the index $t$ temporarily and compare a given plan
$\bar{\mathbf{u}}_{1:H}$ and its associated dynamics $\mathbf{x}_{1:H}$ with
an alternative plan $\bar{\mathbf{u}}_{1:H}^{\prime}$ and its associated
dynamics $\mathbf{x}_{1:H}^{\prime}$, where these dynamics share the noise
sequences $\eta_{1:H},\xi_{1:H}$. We will abbreviate

$\displaystyle\rho(\theta,\theta^{\prime\prime})=\rho(\theta,\theta^{\prime},\bm{\eta}_{1:H},\bm{\xi}_{1:H},\theta)=\left|\left|\theta-\theta^{\prime}\right|\right|_{1}+\sum_{h=1}^{H}\left|\left|\mathbf{x}_{h}-\mathbf{x}_{h}^{\prime}\right|\right|.$
(H.4)

We will also abbreviate $k_{h}=k_{h}(\mathbf{v}_{h})$ and
$k_{h}^{\prime}=k_{h}(\mathbf{v}_{h}^{\prime})$. We begin by proving the
following lemma:

######  Lemma H.1.

Consider the event

$\displaystyle\mathcal{A}_{h}=\left\\{k_{h^{\prime}}=k_{h^{\prime}}^{\prime}\text{
for all }h^{\prime}<h\text{ and }k_{h}\neq k_{h}^{\prime}\right\\}.$ (H.5)

Then for all $h\in[H]$,

$\displaystyle\left|\left|\mathbf{x}_{h}-\mathbf{x}_{h}^{\prime}\right|\right|_{1}\leq
L\cdot\left|\left|\theta-\theta^{\prime}\right|\right|_{1}+2D\cdot\sum_{h^{\prime}=1}^{h-1}\mathbb{I}\left[\mathcal{A}_{h^{\prime}}\right].$
(H.6)

###### Proof.

By (5.1), we have

$\displaystyle\left|\left|\mathbf{x}_{h}-\mathbf{x}_{h}^{\prime}\right|\right|_{1}$
$\displaystyle=\left|\left|g_{k_{h-1}}(\mathbf{v}_{h-1})-g_{k_{h-1}^{\prime}}(\mathbf{v}_{h-1}^{\prime})\right|\right|_{1}$
(H.7)
$\displaystyle\leq\left|\left|g_{k_{h-1}}(\mathbf{v}_{h-1})-g_{k_{h-1}}(\mathbf{v}_{h-1}^{\prime})\right|\right|_{1}\cdot\mathbb{I}\left[\bigcup_{h^{\prime}\geq
h}\mathcal{A}_{h^{\prime}}\right]+2D\cdot\mathbb{I}\left[\bigcup_{h^{\prime}<h}\mathcal{A}_{h^{\prime}}\right]$
(H.8)
$\displaystyle\leq\left|\left|G(\theta,k_{1:H})-G\left(\theta^{\prime},k_{1:H}^{\prime}\right)\right|\right|+2D\cdot\mathbb{I}\left[\bigcup_{h^{\prime}<h}\mathcal{A}_{h^{\prime}}\right]$
(H.9) $\displaystyle\leq
L\cdot\left|\left|\bar{\mathbf{u}}_{1:H}-\bar{\mathbf{u}}_{1:H}^{\prime}\right|\right|_{1}+2D\sum_{h^{\prime}=1}^{h-1}\mathbb{I}\left[\mathcal{A}_{h^{\prime}}\right],$
(H.10)

where the equality is by construction, the first inequality follows from the
boundedness of $\mathcal{Z}$, the second inequality follows from the fact that
the definition of $\mathcal{A}_{h^{\prime}}$ for $h^{\prime}\geq h$ implies
that the modes $k_{h^{\prime\prime}}$ for $h^{\prime\prime}<h$ are the same as
$k_{h^{\prime\prime}}^{\prime}$, and the last inequality follows from a union
bound and the second condition in Theorem 10. The result follows. ∎

We are now ready to prove the pseudo-isometry property:

######  Lemma H.2.

Let $\mathcal{M}$ denote the class of distributions induced by the setup in
Theorem 10 and let $\rho$ be as in (H.4). Then $\rho$ satisfies the pseudo-
isometry property with respect to $\left|\left|\cdot\right|\right|_{1}$ with
$\alpha=\frac{6DH^{2}K^{2}L}{\gamma\sigma_{\mathrm{dir}}}$ and $\beta=1$,
i.e.,

$\displaystyle\sup_{\nu\in\mathcal{M}}\mathbb{E}_{\nu}\left[\rho(\theta,\theta^{\prime})\right]\leq\frac{6DH^{2}K^{2}L}{\gamma\sigma_{\mathrm{dir}}}\cdot\left|\left|\theta-\theta^{\prime}\right|\right|_{1}.$
(H.11)

###### Proof.

By (H.4) and Lemma H.1, it holds that

$\displaystyle\sup_{\nu\in\mathcal{M}}\mathbb{E}_{\nu}\left[\rho(\theta,\theta^{\prime})\right]$
$\displaystyle=\sup_{\nu\in\mathcal{M}}\mathbb{E}_{\nu}\left[\left|\left|\theta-\theta^{\prime}\right|\right|_{1}+\sum_{h=1}^{H}\left|\left|\mathbf{x}_{h}-\mathbf{x}_{h}^{\prime}\right|\right|\right]$
(H.12) $\displaystyle\leq
2LH\cdot\left|\left|\theta-\theta^{\prime}\right|\right|_{1}+2DH\cdot\sup_{\nu\in\mathcal{M}}\sum_{h=1}^{H}\mathbb{P}_{\nu}(\mathcal{A}_{h}).$
(H.13)

We now compute,

$\displaystyle\mathbb{P}(\mathcal{A}_{h})$
$\displaystyle=\mathbb{P}\left(k_{h^{\prime}}=k_{h^{\prime}}^{\prime}\text{
for }h^{\prime}<h\text{ and }k_{h}\neq k_{h}^{\prime}\right)$ (H.14)
$\displaystyle=\mathbb{P}\left(k_{h^{\prime}}=k_{h^{\prime}}^{\prime}\text{
for }h^{\prime}<h\text{ and
}\operatorname*{arg\,max}_{k\in[K]}\left\langle\mathbf{w}_{k,h}^{\star},(\mathbf{v}_{h},1)\right\rangle\neq\operatorname*{arg\,max}_{k^{\prime}\in[K]}\left\langle\mathbf{w}_{k^{\prime},h}^{\star},(\mathbf{v}_{h}^{\prime},1)\right\rangle\right)$
(H.15) $\displaystyle\leq\sum_{k\neq
k^{\prime}\in[K]}\mathbb{P}\left(k_{h^{\prime}}=k_{h^{\prime}}^{\prime}\text{
for }h^{\prime}<h\text{ and
}\left\langle\mathbf{w}_{k,h}^{\star}-\mathbf{w}_{k^{\prime},h}^{\star},(\mathbf{v}_{h},1)\right\rangle\geq
0>\left\langle\mathbf{w}_{k,h}^{\star}-\mathbf{w}_{k^{\prime},h}^{\star},(\mathbf{v}_{h}^{\prime},1)\right\rangle\right),$
(H.16)

where the argument is similar to that in (F.5). For fixed $k\neq
k^{\prime}\in[K]$, we then compute

$\displaystyle\mathbb{P}$
$\displaystyle\left(k_{h^{\prime}}=k_{h^{\prime}}^{\prime}\text{ for
}h^{\prime}<h\text{ and
}\left\langle\mathbf{w}_{k,h}^{\star}-\mathbf{w}_{k^{\prime},h}^{\star},(\mathbf{v}_{h},1)\right\rangle\geq
0>\left\langle\mathbf{w}_{k,h}^{\star}-\mathbf{w}_{k^{\prime},h}^{\star},(\mathbf{v}_{h}^{\prime},1)\right\rangle\right)$
(H.17)
$\displaystyle\leq\mathbb{P}\left(k_{h^{\prime}}=k_{h^{\prime}}^{\prime}\text{
for }h^{\prime}<h\text{ and
}\left|\left\langle\mathbf{w}_{k,h}^{\star}-\mathbf{w}_{k^{\prime},h}^{\star},(\mathbf{v}_{h},1)\right\rangle\right|\leq\left|\left\langle\mathbf{w}_{k,h}^{\star}-\mathbf{w}_{k^{\prime},h}^{\star},(\mathbf{v}_{h}-\mathbf{v}_{h}^{\prime},0)\right\rangle\right|\right)$
(H.18)
$\displaystyle\leq\mathbb{P}\left(k_{h^{\prime}}=k_{h^{\prime}}^{\prime}\text{
for }h^{\prime}<h\text{ and
}\left|\left\langle\mathbf{w}_{k,h}^{\star}-\mathbf{w}_{k^{\prime},h}^{\star},(\mathbf{v}_{h},1)\right\rangle\right|\leq
2\cdot\left|\left|\mathbf{v}_{h}-\mathbf{v}_{h}^{\prime}\right|\right|_{1}\right),$
(H.19)

where the first inequality follows from the triangle inequality and the second
from Hölder’s inequality. We now observe that

$\displaystyle\left|\left|\mathbf{v}_{h}-\mathbf{v}_{h}^{\prime}\right|\right|_{1}$
$\displaystyle\leq\left|\left|\mathbf{u}_{h}-\mathbf{u}_{h}^{\prime}\right|\right|_{1}+\left|\left|\mathbf{x}_{h}-\mathbf{x}_{h}^{\prime}\right|\right|_{1},$
(H.20)

and, furthermore, because the mode sequences $k_{1:h-1}=k_{1:h-1}^{\prime}$,
we have in this event that

$\displaystyle\left|\left|\mathbf{x}_{h}-\mathbf{x}_{h}^{\prime}\right|\right|_{1}$
$\displaystyle\leq\left|\left|G(\theta,k_{1:H})-G(\theta^{\prime},k_{1:H})\right|\right|_{1}\leq
L\cdot\left|\left|\theta-\theta^{\prime}\right|\right|_{1}.$ (H.21)

Thus, we have

$\displaystyle\mathbb{P}$
$\displaystyle\left(k_{h^{\prime}}=k_{h^{\prime}}^{\prime}\text{ for
}h^{\prime}<h\text{ and
}\left|\left\langle\mathbf{w}_{k,h}^{\star}-\mathbf{w}_{k^{\prime},h}^{\star},(\mathbf{v}_{h},1)\right\rangle\right|\leq
2\cdot\left|\left|\mathbf{v}_{h}-\mathbf{v}_{h}^{\prime}\right|\right|_{1}\right)$
(H.22)
$\displaystyle\leq\mathbb{P}\left(\left|\left\langle\mathbf{w}_{k,h}^{\star}-\mathbf{w}_{k^{\prime},h}^{\star},\mathbf{v}_{h}\right\rangle\right|\leq
3L\cdot\left|\left|\theta-\theta^{\prime}\right|\right|_{1}\right)$ (H.23)
$\displaystyle=\mathbb{P}\left(\left|\left\langle\frac{\mathbf{w}_{k,h}^{\star}-\mathbf{w}_{k^{\prime},h}^{\star}}{\left|\left|\mathbf{w}_{k,h,\widehat{d}}^{\star}-\mathbf{w}_{k^{\prime},h,\widehat{d}}^{\star}\right|\right|_{2}},(\mathbf{v}_{h},1)\right\rangle\right|\leq\frac{3L}{\left|\left|\mathbf{w}_{k,h,\widehat{d}}^{\star}-\mathbf{w}_{k^{\prime},h,\widehat{d}}^{\star}\right|\right|_{2}}\cdot\left|\left|\theta-\theta^{\prime}\right|\right|_{1}\right)$
(H.24)
$\displaystyle\leq\frac{3L}{\sigma_{\mathrm{dir}}\cdot\left|\left|\mathbf{w}_{k,h,\widehat{d}}^{\star}-\mathbf{w}_{k^{\prime},h,\widehat{d}}^{\star}\right|\right|_{2}}\cdot\left|\left|\theta-\theta^{\prime}\right|\right|_{1}$
(H.25)
$\displaystyle\leq\frac{3L}{\sigma_{\mathrm{dir}}\gamma}\cdot\left|\left|\theta-\theta^{\prime}\right|\right|_{1},$
(H.26)

where the first inequality follows from the preceding computation, the
equality is trivial, the second inequality follows from the assmption of
directional smoothness, and the last inequality follows from the margin
assumption. Plugging back in, the result follows. ∎

Finally, we prove that the bracketing numbers can be controlled:

######  Lemma H.3.

Let $\mathcal{M}$ and $\rho$ be as in Lemma H.2 and $\mathcal{K}$ be as in
Theorem 10. Then, for any $\epsilon>0$, it holds that

$\displaystyle\mathcal{N}_{\mathcal{M},[]}\left(\mathcal{K},\rho,\epsilon\right)\leq\left(\frac{36K^{2}DH^{2}L}{\gamma\sigma_{\mathrm{dir}}\epsilon}\right)^{H(d+1)}.$
(H.27)

###### Proof.

Let $\mathcal{N}=\left\\{\theta^{i}\right\\}\subset\mathcal{U}^{\times H}$
denote an $\widetilde{\epsilon}$-net with respect to $\ell_{1}$, where
$\widetilde{\epsilon}=\frac{\gamma\sigma_{\mathrm{dir}}}{12DH^{2}L}\cdot\epsilon$.
As in Lemmas F.3 and G.3, we will show that if $\mathcal{B}_{i}$ denotes the
set of $\theta$ with distance at most $\widetilde{\epsilon}$ to $\theta^{i}$,
then $\left\\{(\theta^{i},\mathcal{B}_{i})\right\\}$ forms a generalized
$\epsilon$-bracket with respect to $\mathcal{M}$. The argument is essentially
identical after we replace Lemmas F.1 and G.1 with Lemma H.1 and the argument
in Lemma H.2. In particular, for fixed $i$ and any $\nu\in\mathcal{M}$, we see
that

$\displaystyle\mathbb{E}_{\nu}\left[\sup_{\theta\in\mathcal{B}_{i}}\rho(\theta,\theta^{i})\right]$
$\displaystyle=\mathbb{E}_{\nu}\left[\sup_{\theta\in\mathcal{B}_{i}}\left|\left|\theta-\theta^{i}\right|\right|_{1}+\sum_{h=1}^{H}\left|\left|\mathbf{x}_{h}-\mathbf{x}_{h}^{i}\right|\right|_{1}\right]$
(H.28)
$\displaystyle\leq\widetilde{\epsilon}+\mathbb{E}_{\nu}\left[\sup_{\theta\in\mathcal{B}_{i}}\sum_{h=1}^{H}\left|\left|\mathbf{x}_{h}-\mathbf{x}_{h}^{i}\right|\right|_{1}\right],$
(H.29)

where we let $\mathbf{x}_{1:H}^{i}$ denote the dynamics evolved with
$\theta^{i}$. For the second term, we invoke Lemma H.1 and compute:

$\displaystyle\mathbb{E}_{\nu}\left[\sup_{\theta\in\mathcal{B}_{i}}\sum_{h=1}^{H}\left|\left|\mathbf{x}_{h}-\mathbf{x}_{h}^{i}\right|\right|_{1}\right]$
$\displaystyle\leq\sum_{h=1}^{H}\mathbb{E}_{\nu}\left[\sup_{\theta\in\mathcal{B}_{i}}\left|\left|\mathbf{x}_{h}-\mathbf{x}_{h}^{i}\right|\right|_{1}\right]$
(H.30)
$\displaystyle\leq\sum_{h=1}^{H}\mathbb{E}_{\nu}\left[\sup_{\theta\in\mathcal{B}_{i}}L\cdot\left|\left|\theta-\theta^{i}\right|\right|+2D\cdot\sum_{h^{\prime}=1}^{h-1}\mathbb{I}\left[\mathcal{A}_{h^{\prime}}\right]\right]$
(H.31) $\displaystyle\leq
LH\widetilde{\epsilon}+2DH^{2}\cdot\max_{h\in[H]}\mathbb{E}_{\nu}\left[\sup_{\theta\in\mathcal{B}_{i}}\mathbb{I}\left[\mathcal{A}_{h}\right]\right].$
(H.32)

Now we reason in a similar manner as in Lemma H.2:

$\displaystyle\mathbb{E}_{\nu}\left[\sup_{\theta\in\mathcal{B}_{i}}\mathbb{I}\left[\mathcal{A}_{h}\right]\right]$
$\displaystyle=\mathbb{P}\left(\bigcup_{\bar{\mathbf{u}}_{1:H}\in\mathcal{B}_{i}}\left\\{k_{h^{\prime}}=k_{h^{\prime}}^{i}\text{
for }h^{\prime}<h\text{ and }k_{h}\neq k_{h}^{i}\right\\}\right)$ (H.33)
$\displaystyle\leq\sum_{k\neq
k^{\prime}\in[K]}\mathbb{P}\left(\bigcup_{\theta\in\mathcal{B}_{i}}\left\\{k_{h^{\prime}}=k_{h^{\prime}}^{i}\text{
for }h^{\prime}<h\text{ and
}\left|\left\langle\mathbf{w}_{k,h}^{\star}-\mathbf{w}_{k^{\prime},h}^{\star},(\mathbf{v}_{h}^{i},1)\right\rangle\right|\leq
2\cdot\left|\left|\mathbf{v}_{h}-\mathbf{v}_{h}^{i}\right|\right|_{1}\right\\}\right),$
(H.34)

where the inequality follows from the same chain of logic as in (H.16) and
(H.16). As in (H.21), we observe that if the mode sequence
$k_{h^{\prime}}=k_{h^{\prime}}^{i}$ for $h^{\prime}<h$, then

$\displaystyle\left|\left|\mathbf{v}_{h}-\mathbf{v}_{h}^{i}\right|\right|_{1}\leq
2L\cdot\left|\left|\theta-\theta^{i}\right|\right|_{1}.$ (H.35)

Thus, by construction of $\mathcal{B}_{i}$, we see that

$\displaystyle\mathbb{P}$
$\displaystyle\left(\bigcup_{\theta\in\mathcal{B}_{i}}\left\\{k_{h^{\prime}}=k_{h^{\prime}}^{i}\text{
for }h^{\prime}<h\text{ and
}\left|\left\langle\mathbf{w}_{k,h}^{\star}-\mathbf{w}_{k^{\prime},h}^{\star},(\mathbf{v}_{h}^{i},1)\right\rangle\right|\leq
2\cdot\left|\left|\mathbf{v}_{h}-\mathbf{v}_{h}^{i}\right|\right|_{1}\right\\}\right)$
(H.36)
$\displaystyle\leq\mathbb{P}\left(\bigcup_{\theta\in\mathcal{B}_{i}}\left\\{\left|\left\langle\mathbf{w}_{k,h}^{\star}-\mathbf{w}_{k^{\prime},h}^{\star},(\mathbf{v}_{h}^{i},1)\right\rangle\right|\leq
6L\cdot\left|\left|\theta-\theta^{i}\right|\right|_{1}\right\\}\right)$ (H.37)
$\displaystyle\leq\mathbb{P}\left(\left|\left\langle\mathbf{w}_{k,h}^{\star}-\mathbf{w}_{k^{\prime},h}^{\star},(\mathbf{v}_{h}^{i},1)\right\rangle\right|\leq
6L\widetilde{\epsilon}\right)$ (H.38)
$\displaystyle\leq\frac{6L\widetilde{\epsilon}}{\gamma\sigma_{\mathrm{dir}}},$
(H.39)

where the last inequality follows from directional smoothness and the margin
assumption, as in (H.26). Plugging back in to the definition of
$\widetilde{\epsilon}$, we see that
$\left\\{(\theta^{i},\mathcal{B}_{i})\right\\}$ forms a generalized
$\epsilon$-bracket as desired. Note that $\mathcal{K}$ lives in the $\ell_{1}$
ball of radius $D$ inside of $\mathbb{R}^{dH}$; thus, applying the same
argument as in Theorem 2 concludes the proof. ∎

Finally, we are ready to prove the main result:

###### Proof of Theorem 10.

By Theorem 1, it suffices to show that the loss is Lipschitz with respect to
$\rho$. To do this, note that

$\displaystyle\ell(\mathbf{z}_{t})-\ell(\mathbf{z}_{t}^{\prime})$
$\displaystyle\leq\left|\left|\mathbf{v}_{t,1:H}-\mathbf{v}_{t,1:H}^{\prime}\right|\right|_{1}$
(H.40)
$\displaystyle\leq\left|\left|\theta-\theta^{\prime}\right|\right|_{1}+\sum_{h=1}^{H}\left|\left|\mathbf{x}_{t,h}-\mathbf{x}_{t,h}^{\prime}\right|\right|_{1}$
(H.41) $\displaystyle=\rho(\theta,\theta^{\prime}).$ (H.42)

Thus by Theorem 1, it holds that if the learner plays Algorithm 2 with
$n=\sqrt{\eta}$, then he experiences

$\displaystyle\mathbb{E}\left[\operatorname{Reg}_{T}\right]\leq\operatorname{\widetilde{\mathcal{O}}}\left({\eta+\frac{TDH^{2}K^{2}L}{\gamma\sigma_{\mathrm{dir}}}\cdot\sqrt{\frac{Hd}{\eta}}}\right)$
(H.43)

by appealing to Lemmas H.2 and H.3. Setting $\eta$ as in the statement of the
theorem concludes the proof. ∎

Finally, we prove an analogue of Theorem 10 where we now assume that the
decision boundaries between modes are polynomials. The statement is almost
equivalent to that of Theorem 10, with the exception that the boundaries
between modes are now parameterized by polynomials, with the resulting
increased oracle complexity along the lines of Theorem 3. The statement is as
follows:

######  Theorem 11.

Suppose that we are in the situation of (5.1), with the exception that the
regions are defined by polynomials of degree at most $r$. More precisely, we
suppose that

$\displaystyle\mathbf{x}_{t,h+1}(\theta)$
$\displaystyle=g_{t,h,k_{t,h}(\mathbf{v}_{t,h}(\theta))}(\mathbf{v}_{t,h}(\theta))+\bm{\eta}_{t,h},\quad\text{and
}$ (H.44) $\displaystyle\mathbf{u}_{t,h}(\theta)$
$\displaystyle=\bar{\mathbf{u}}_{t,h}+\bm{\xi}_{t,h},\quad\mathbf{v}_{t,h}(\theta)=(\mathbf{x}_{t,h}(\theta),\quad\mathbf{u}_{t,h}(\theta)),$
(H.45) $\displaystyle k_{t,h}(\mathbf{v})$
$\displaystyle=\operatorname*{arg\,max}_{k\in[K]}\phi_{t,h}(k,\mathbf{v}),\quad\text{and}\quad\phi_{t,h}(k,\mathbf{v})=f_{\mathbf{w}_{t,k,h}}(\mathbf{v}),$
(H.46)

where the $f_{\mathbf{w}_{t,k,h}}$ are degree $r$ polynomials with
$\mathbf{w}_{t,k,h}$ parameterizing the coefficients. Suppose that for all
$t\in[T]$, the following properties hold almost surely under the adversary’s
strategy $p_{t}$:

  1. 1.

$\mathbf{x}_{t,1}\mid\mathcal{F}_{t}$ and
$(\bm{\eta}_{t,h},\bm{\xi}_{t,h})\mid\mathcal{F}_{t,h-1}$ are
$\sigma_{\mathrm{poly},r}$-polynomially smooth.

  2. 2.

For all mode sequences $k_{1:H}\in[K]^{H}$ and
$\theta,\theta^{\prime}\in\mathcal{U}^{\times H}$,
$\left|\left|G_{t}(\theta,k_{1:H})-G_{t}(\theta^{\prime},k_{1:H})\right|\right|\leq
L\left|\left|\theta-\theta^{\prime}\right|\right|_{1}$, i.e., the functions
$G_{t}$ are $L$-Lipschitz with respect to the $\ell_{1}$ norm, where the
$G_{t}$ are the maps defined in Definition H.1.

  3. 3.

For all $h\in[H]$,
$\sup_{\theta\in\mathcal{K}}\left|\left|\mathbf{u}_{t,h}(\theta)\right|\right|_{1}\vee\left|\left|\mathbf{x}_{t,h}(\theta)\right|\right|_{1}\leq
D$.

  4. 4.

For some $\gamma>0$, it holds for all $h\in[H]$ that $\min_{k\neq
k^{\prime}\in[K]}\mathrm{coeff}_{r}\left(f_{\mathbf{w}_{t,k,h}}-f_{\mathbf{w}_{t,k^{\prime},h}}\right)\geq\gamma$,
where $\mathrm{coeff}_{r}(\cdot)$ is as defined in Definition 4.1.

  5. 5.

For all $\mathbf{v}_{1:H},\mathbf{v}_{1:H}^{\prime}\in\mathcal{V}^{H}$ with
$\|\mathbf{v}_{1:H}\|_{1}\vee\|\mathbf{v}_{1:H}^{\prime}\|_{1}\leq 2D$, we
have that the loss functions $\ell^{v}_{t}$ are Lipschitz with respect to the
$\ell_{1}$ norm and bounded, i.e.,
$|\ell^{v}_{t}(\mathbf{v}_{1:H})-\ell^{v}_{t}(\mathbf{v}_{1:H}^{\prime})|\leq\|\mathbf{v}_{1:H}-\mathbf{v}_{1:H}\|_{1}$
and $|\ell^{v}_{t}(\mathbf{v}_{1:H})|\leq 1$.

  6. 6.

The coefficients $\mathbf{w}_{t,k,h}$ of the polynomials
$f_{\mathbf{w}_{t,k,h}}$ have unit Euclidean norm.

If the planner plays $\theta_{t}$ according to Algorithm 2 with
$\eta=\left(\frac{LTK^{2}r^{2}H^{2+r}d^{r}DB}{\gamma\sigma_{\mathrm{poly},r}}\right)^{\frac{4r-2}{4r-1}}$
and $n=\sqrt{\eta}$, then

$\displaystyle\mathbb{E}\left[\operatorname{Reg}_{T}\right]\leq\operatorname{\widetilde{\mathcal{O}}}\left({\left(\frac{LTK^{2}r^{2}H^{2+r}d^{r}DB}{\gamma\sigma_{\mathrm{poly},r}}\right)^{\frac{4r-2}{4r-1}}}\right).$
(H.47)

Thus, the oracle complexity of achieving average regret $\epsilon$ is
$\operatorname{\widetilde{\mathcal{O}}}\left({\left(\frac{LK^{2}r^{2}H^{2+r}d^{r}DB}{\gamma\sigma_{\mathrm{poly},r}}\right)^{\frac{4r-2}{4r-1}}}\right)\cdot\epsilon^{-\frac{2}{r}}$.

###### Proof.

The proof will be similar to that of Theorem 10. In particular, we will still
use the same $\rho$ as in (H.4) and preserve notation from that proof.
Applying Theorem 1, it suffices to control the pseudo-isometry and generalized
bracketing numbers. We first claim that if $\mathcal{M}$ is the class of
distributions for the adversary, induced by the setting at hand, then

$\displaystyle\sup_{\nu\in\mathcal{M}}\mathbb{E}_{\nu}\left[\rho(\theta,\theta^{\prime})\right]\leq\frac{4D^{2}H^{2}K^{2}L}{\gamma^{\frac{1}{r}}\cdot\sigma_{\mathrm{poly},r}}\cdot\left|\left|\theta-\theta^{\prime}\right|\right|_{1}^{\frac{1}{r}}.$
(H.48)

To see this, we observe that if $\mathcal{A}_{h}$ is as in Lemma H.1, then by
that same result,

$\displaystyle\sup_{\nu\in\mathcal{M}}\mathbb{E}_{\nu}\left[\rho(\theta,\theta^{\prime})\right]$
$\displaystyle=\sup_{\nu\in\mathcal{M}}\mathbb{E}_{\nu}\left[\left|\left|\theta-\theta^{\prime}\right|\right|+\sum_{h=1}^{H}\left|\left|\mathbf{x}_{h}-\mathbf{x}_{h}^{\prime}\right|\right|\right]$
(H.49) $\displaystyle\leq
2LH\cdot\left|\left|\theta-\theta^{\prime}\right|\right|_{1}+2DH\cdot\sup_{\nu\in\mathcal{M}}\sum_{h=1}^{H}\mathbb{P}_{\nu}\left(\mathcal{A}_{h}\right).$
(H.50)

We now compute, as in Lemma H.2,

$\displaystyle\mathbb{P}\left(\mathcal{A}_{h}\right)$
$\displaystyle=\mathbb{P}\left(k_{h^{\prime}}=k_{h^{\prime}}^{\prime}\text{
for }h^{\prime}<h\text{ and }k_{h}\neq k_{h}^{\prime}\right)$ (H.51)
$\displaystyle\leq\sum_{k\neq
k^{\prime}\in[K]}\mathbb{P}\left(k_{h^{\prime}}=k_{h^{\prime}}^{\prime}\text{
for }h^{\prime}<h\text{ and
}f_{\mathbf{w}_{k,h}}(\mathbf{v}_{h})-f_{\mathbf{w}_{k^{\prime},h}}(\mathbf{v}_{h})\geq
0>f_{\mathbf{w}_{k,h}}(\mathbf{v}_{h}^{\prime})-f_{\mathbf{w}_{k^{\prime},h}}(\mathbf{v}_{h}^{\prime})\right).$
(H.52)

For fixed $k\neq k^{\prime}$, we then compute

$\displaystyle\mathbb{P}$
$\displaystyle\left(k_{h^{\prime}}=k_{h^{\prime}}^{\prime}\text{ for
}h^{\prime}<h\text{ and
}f_{\mathbf{w}_{k,h}}(\mathbf{v}_{h})-f_{\mathbf{w}_{k^{\prime},h}}(\mathbf{v}_{h})\geq
0>f_{\mathbf{w}_{k,h}}(\mathbf{v}_{h}^{\prime})-f_{\mathbf{w}_{k^{\prime},h}}(\mathbf{v}_{h}^{\prime})\right)$
(H.53)
$\displaystyle\leq\mathbb{P}\left(k_{h^{\prime}}=k_{h^{\prime}}^{\prime}\text{
for }h^{\prime}<h\text{ and
}\left|f_{\mathbf{w}_{k,h}}(\mathbf{v}_{h})-f_{\mathbf{w}_{k^{\prime},h}}(\mathbf{v}_{h})\right|\leq\left|f_{\mathbf{w}_{k,h}}(\mathbf{v}_{h}^{\prime})-f_{\mathbf{w}_{k^{\prime},h}}(\mathbf{v}_{h}^{\prime})\right|+\left|f_{\mathbf{w}_{k,h}}(\mathbf{v}_{h})-f_{\mathbf{w}_{k^{\prime},h}}(\mathbf{v}_{h})\right|\right)$
(H.54)
$\displaystyle\leq\mathbb{P}\left(k_{h^{\prime}}=k_{h^{\prime}}^{\prime}\text{
for }h^{\prime}<h\text{ and
}\left|f_{\mathbf{w}_{k,h}}(\mathbf{v}_{h})-f_{\mathbf{w}_{k^{\prime},h}}(\mathbf{v}_{h})\right|\leq
2D^{r}\cdot\left|\left|\mathbf{v}_{h}-\mathbf{v}_{h}^{\prime}\right|\right|_{1}\right),$
(H.55)

where the second inequality follows from the assumption that
$\mathbf{w}_{k,h}$ have unit norm, the fact that power functions area locally
Lipschitz, and the fact that $\mathbf{v}_{h}$ has norm bounded by $D$.
Applying the assumption of polynomial smoothness, we see that this last
expression is bounded above:

$\displaystyle\mathbb{P}$
$\displaystyle\left(k_{h^{\prime}}=k_{h^{\prime}}^{\prime}\text{ for
}h^{\prime}<h\text{ and
}\left|f_{\mathbf{w}_{k,h}}(\mathbf{v}_{h})-f_{\mathbf{w}_{k^{\prime},h}}(\mathbf{v}_{h})\right|\leq
2D^{r}\cdot\left|\left|\mathbf{v}_{h}-\mathbf{v}_{h}^{\prime}\right|\right|_{1}\right)$
(H.56)
$\displaystyle\leq\frac{2D}{\gamma^{\frac{1}{r}}\cdot\sigma_{\mathrm{poly},r}}\left|\left|\mathbf{v}_{h}-\mathbf{v}_{h^{\prime}}\right|\right|_{1}^{\frac{1}{r}}.$
(H.57)

We now conclude in a similar manner as in Lemma H.2 and observe that

$\displaystyle\left|\left|\mathbf{v}_{h}-\mathbf{v}_{h}^{\prime}\right|\right|_{1}^{\frac{1}{r}}\leq
2\left|\left|\mathbf{u}_{h}-\mathbf{u}_{h}^{\prime}\right|\right|_{1}^{\frac{1}{r}}+2\left|\left|\mathbf{x}_{h}-\mathbf{x}_{h}^{\prime}\right|\right|_{1}^{\frac{1}{r}}$
(H.58)

and because the mode sequences $k_{1:h-1}=k_{1:h-1}^{\prime}$ on this event,

$\displaystyle\left|\left|\mathbf{x}_{h}-\mathbf{x}_{h}^{\prime}\right|\right|_{1}^{\frac{1}{r}}\leq
L^{\frac{1}{r}}\cdot\left|\left|\theta-\theta^{\prime}\right|\right|_{1}^{\frac{1}{r}}.$
(H.59)

Putting everything together suffices to prove that (H.48) holds.

We now claim that for $0<\epsilon<1$,

$\displaystyle\mathcal{N}_{\mathcal{M},[]}\left(\Theta,\mathcal{M},\epsilon\right)\leq\left(\frac{12D^{2}H^{2}K^{2}L}{\sigma_{\mathrm{poly},r}\gamma^{\frac{1}{r}}}\epsilon\right)^{K^{2}r^{2}(Hd)^{r}}.$
(H.60)

To see this, we let
$\mathcal{N}=\left\\{\theta^{i}\right\\}\subset\mathcal{U}^{\times H}$ denote
an $\widetilde{\epsilon}$-net with respect to $\ell_{1}$, where
$\widetilde{\epsilon}=\gamma\left(\frac{\sigma_{\mathrm{poly},r}}{4D^{2}H^{2}K^{2}L}\cdot\epsilon\right)^{r}$.
Our proof proceeds similarly to that in Lemma H.3 and we demonstrate that if
$\mathcal{B}_{i}$ denots the set of $\widetilde{\epsilon}$-balls around
$\theta^{i}$ then the associated $(\theta^{i},\mathcal{B}_{i})$ forms a
generalized $\epsilon$-bracket with respect to $\mathcal{M}$. Indeed, for
fixed $i$ and $\nu\in\mathcal{M}$, we have:

$\displaystyle\mathbb{E}_{\nu}\left[\sup_{\theta\in\mathcal{B}_{i}}\rho(\theta,\theta^{i})\right]$
$\displaystyle\leq\widetilde{\epsilon}+\mathbb{E}_{\nu}\left[\sup_{\theta\in\mathcal{B}_{i}}\sum_{h=1}^{H}\left|\left|\mathbf{x}_{h}-\mathbf{x}_{h}^{i}\right|\right|_{1}\right].$
(H.61)

For the second term, we again invoke Lemma H.1 and observe that

$\displaystyle\mathbb{E}_{\nu}\left[\sup_{\theta\in\mathcal{B}_{i}}\sum_{h=1}^{H}\left|\left|\mathbf{x}_{h}-\mathbf{x}_{h}^{i}\right|\right|_{1}\right]$
$\displaystyle\leq\sum_{h=1}^{H}\mathbb{E}_{\nu}\left[\sup_{\theta\in\mathcal{B}_{i}}L\cdot\left|\left|\theta-\theta^{i}\right|\right|_{1}+2D\cdot\sum_{h^{\prime}=1}^{h-1}\mathbb{I}\left[\mathcal{A}_{h^{\prime}}\right]\right]$
(H.62) $\displaystyle\leq
LH\widetilde{\epsilon}+2DH^{2}\cdot\max_{h\in[H]}\mathbb{E}_{\nu}\left[\sup_{\theta\in\mathcal{B}_{i}}\mathbb{I}\left[\mathcal{A}_{h}\right]\right].$
(H.63)

Using the identical logic combining as in Lemma H.3, but using the polynomial
smoothness assumptions in the same way as in Lemma G.3, we see that

$\displaystyle\mathbb{P}_{\nu}\left(\mathcal{A}_{h}\right)$
$\displaystyle\leq\sum_{k\neq
k^{\prime}\in[K]}\mathbb{P}\left(\bigcup_{\theta\in\mathcal{B}_{i}}\left\\{k_{h^{\prime}}=k_{h^{\prime}}^{i}\text{
for }h^{\prime}<h\text{ and
}\left|f_{\mathbf{w}_{k,h}}(\mathbf{v}_{h}^{i})-f_{\mathbf{w}_{k^{\prime},h}}(\mathbf{v}_{h}^{i})\right|\leq
2D^{r}\cdot\left|\left|\mathbf{v}_{h}-\mathbf{v}_{h}^{i}\right|\right|_{1}\right\\}\right).$
(H.64)

Observing once again that

$\displaystyle\left|\left|\mathbf{v}_{h}-\mathbf{v}_{h}^{i}\right|\right|_{1}\leq
2L\cdot\left|\left|\theta-\theta^{i}\right|\right|$ (H.65)

by the Lipschitzness of the $G_{t}$, we see that

$\displaystyle\mathbb{P}_{\nu}\left(\mathcal{A}_{h}\right)$
$\displaystyle\leq\sum_{k\neq
k^{\prime}\in[K]}\mathbb{P}\left(\bigcup_{\theta\in\mathcal{B}_{i}}\left\\{k_{h^{\prime}}=k_{h^{\prime}}^{i}\text{
for }h^{\prime}<h\text{ and
}\left|f_{\mathbf{w}_{k,h}}(\mathbf{v}_{h}^{i})-f_{\mathbf{w}_{k^{\prime},h}}(\mathbf{v}_{h}^{i})\right|\leq
4D^{r}L\widetilde{\epsilon}\right\\}\right)$ (H.66)
$\displaystyle\leq\sum_{k\neq
k^{\prime}\in[K]}\mathbb{P}\left(\left|f_{\mathbf{w}_{k,h}}(\mathbf{v}_{h}^{i})-f_{\mathbf{w}_{k^{\prime},h}}(\mathbf{v}_{h}^{i})\right|\leq
4D^{r}L\widetilde{\epsilon}\right)$ (H.67) $\displaystyle\leq
K^{2}\frac{4DL^{\frac{1}{r}}}{\gamma^{\frac{1}{r}}\cdot\sigma_{\mathrm{poly},r}}\cdot\widetilde{\epsilon}^{\frac{1}{r}}.$
(H.68)

Plugging everything back in to the above work, we see that indeed
$\mathcal{N}$ is a generalized $\epsilon$-net. Using the same volume argument
as in the proofs of Lemmas F.3, G.3, and H.3, we see that (H.60) holds.

Finally, we note that $\ell^{v}$ is clearly lipschitz with respect to $\rho$
and thus we may apply Theorem 1, which tells us that if we run Algorithm 2,
then for $n=\sqrt{\eta}$,

$\displaystyle\mathbb{E}\left[\operatorname{Reg}_{T}\right]\leq\operatorname{\widetilde{\mathcal{O}}}\left({\eta+\frac{T}{n}K^{2}r^{2}H^{r}d^{r}\log\left(\frac{1}{\sigma_{\mathrm{poly},r}}\right)+\frac{TD}{\gamma^{\frac{1}{r}}\sigma_{\mathrm{poly},r}}\cdot\left(\frac{K^{2}r^{2}H^{r}d^{r}}{\eta}\right)^{\frac{1}{4r-2}}}\right).$
(H.69)

Setting $\eta$ as in the statement then concludes the proof. ∎