Minimax Regret for Partial Monitoring: Infinite Outcomes and Rustichini's Regret
This work addresses theoretical gaps in online learning for partial monitoring, offering incremental advancements in regret analysis for specialized game settings.
The paper tackles the problem of determining asymptotic minimax regret in finite-action partial monitoring games under two scenarios: infinite latent spaces with standard regret, and finite latent spaces with Rustichini regret, showing that a generalized information ratio governs these bounds. It provides examples where minimax regret scales as n^p for p in [1/2,1] and n^{4/7} up to subpolynomial factors.
We show that a version of the generalised information ratio of Lattimore and Gyorgy (2020) determines the asymptotic minimax regret for all finite-action partial monitoring games provided that (a) the standard definition of regret is used but the latent space where the adversary plays is potentially infinite; or (b) the regret introduced by Rustichini (1999) is used and the latent space is finite. Our results are complemented by a number of examples. For any $p \in [1/2,1]$ there exists an infinite partial monitoring game for which the minimax regret over $n$ rounds is $n^p$ up to subpolynomial factors and there exist finite games for which the minimax Rustichini regret is $n^{4/7}$ up to subpolynomial factors.