Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Bounded Memory Adversarial Bandits with Composite Anonymous Delayed
  Feedback   We study the adversarial bandit problem with composite anonymous delayed
feedback. In this setting, losses of an action are split into $d$ components,
spreading over consecutive rounds after the action is chosen. And in each
round, the algorithm observes the aggregation of losses that come from the
latest $d$ rounds. Previous works focus on oblivious adversarial setting, while
we investigate the harder non-oblivious setting. We show non-oblivious setting
incurs $\Omega(T)$ pseudo regret even when the loss sequence is bounded memory.
However, we propose a wrapper algorithm which enjoys $o(T)$ policy regret on
many adversarial bandit problems with the assumption that the loss sequence is
bounded memory. Especially, for $K$-armed bandit and bandit convex
optimization, we have $\mathcal{O}(T^{2/3})$ policy regret bound. We also prove
a matching lower bound for $K$-armed bandit. Our lower bound works even when
the loss sequence is oblivious but the delay is non-oblivious. It answers the
open problem proposed in \cite{wang2021adaptive}, showing that non-oblivious
delay is enough to incur $\tilde{\Omega}(T^{2/3})$ regret.

14
The categories of this paper are: math-ph
32
The categories of this paper are: atom-ph
24
The categories of this paper are: dg-ga
15
The categories of this paper are: nucl-ex
33
The categories of this paper are: plasm-ph
29
The categories of this paper are: funct-an
7
The categories of this paper are: hep-th
22
The categories of this paper are: chao-dyn
25
The categories of this paper are: patt-sol
31
The categories of this paper are: ao-sci
37
The categories of this paper are: supr-con
10
The categories of this paper are: q-bio
4
The categories of this paper are: cond-mat
13
The categories of this paper are: quant-ph
18
The categories of this paper are: econ
2
The categories of this paper are: math