Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: An Information-Theoretic Approach to Minimax Regret in Partial
  Monitoring   We prove a new minimax theorem connecting the worst-case Bayesian regret and
minimax regret under partial monitoring with no assumptions on the space of
signals or decisions of the adversary. We then generalise the
information-theoretic tools of Russo and Van Roy (2016) for proving Bayesian
regret bounds and combine them with the minimax theorem to derive minimax
regret bounds for various partial monitoring settings. The highlight is a clean
analysis of `non-degenerate easy' and `hard' finite partial monitoring, with
new regret bounds that are independent of arbitrarily large game-dependent
constants. The power of the generalised machinery is further demonstrated by
proving that the minimax regret for k-armed adversarial bandits is at most
sqrt{2kn}, improving on existing results by a factor of 2. Finally, we provide
a simple analysis of the cops and robbers game, also improving best known
constants.

21
The categories of this paper are: adap-org
36
The categories of this paper are: cmp-lg
22
The categories of this paper are: chao-dyn
4
The categories of this paper are: cond-mat
17
The categories of this paper are: q-fin
23
The categories of this paper are: solv-int
24
The categories of this paper are: dg-ga
12
The categories of this paper are: nucl-th
13
The categories of this paper are: quant-ph
37
The categories of this paper are: supr-con
9
The categories of this paper are: nlin
29
The categories of this paper are: funct-an
0
The categories of this paper are: hep-ph
15
The categories of this paper are: nucl-ex
6
The categories of this paper are: astro-ph
35
The categories of this paper are: mtrl-th