Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Adaptive Regret Minimization in Bounded-Memory Games   Online learning algorithms that minimize regret provide strong guarantees in
situations that involve repeatedly making decisions in an uncertain
environment, e.g. a driver deciding what route to drive to work every day.
While regret minimization has been extensively studied in repeated games, we
study regret minimization for a richer class of games called bounded memory
games. In each round of a two-player bounded memory-m game, both players
simultaneously play an action, observe an outcome and receive a reward. The
reward may depend on the last m outcomes as well as the actions of the players
in the current round. The standard notion of regret for repeated games is no
longer suitable because actions and rewards can depend on the history of play.
To account for this generality, we introduce the notion of k-adaptive regret,
which compares the reward obtained by playing actions prescribed by the
algorithm against a hypothetical k-adaptive adversary with the reward obtained
by the best expert in hindsight against the same adversary. Roughly, a
hypothetical k-adaptive adversary adapts her strategy to the defender's actions
exactly as the real adversary would within each window of k rounds. Our
definition is parametrized by a set of experts, which can include both fixed
and adaptive defender strategies.
  We investigate the inherent complexity of and design algorithms for adaptive
regret minimization in bounded memory games of perfect and imperfect
information. We prove a hardness result showing that, with imperfect
information, any k-adaptive regret minimizing algorithm (with fixed strategies
as experts) must be inefficient unless NP=RP even when playing against an
oblivious adversary. In contrast, for bounded memory games of perfect and
imperfect information we present approximate 0-adaptive regret minimization
algorithms against an oblivious adversary running in time n^{O(1)}.

29
The categories of this paper are: funct-an
9
The categories of this paper are: nlin
11
The categories of this paper are: hep-lat
18
The categories of this paper are: econ
8
The categories of this paper are: hep-ex
28
The categories of this paper are: alg-geom
5
The categories of this paper are: gr-qc
0
The categories of this paper are: hep-ph
35
The categories of this paper are: mtrl-th
19
The categories of this paper are: eess
30
The categories of this paper are: q-alg
20
The categories of this paper are: acc-phys
33
The categories of this paper are: plasm-ph
15
The categories of this paper are: nucl-ex
3
The categories of this paper are: physics
31
The categories of this paper are: ao-sci