Best-of-Both-Worlds Algorithms for Partial Monitoring. (arXiv:2207.14550v2 [cs.LG] UPDATED)

This study considers the partial monitoring problem with $k$-actions and
$d$-outcomes and provides the first best-of-both-worlds algorithms, whose
regrets are favorably bounded both in the stochastic and adversarial regimes.
In particular, we show that for non-degenerate locally observable games, the
regret is $O(m^2 k^4 \log(T) \log(k_{\Pi} T) / \Delta_{\min})$ in the
stochastic regime and $O(m k^{2/3} \sqrt{T \log(T) \log k_{\Pi}})$ in the
adversarial regime, where $T$ is the number of rounds, $m$ is the maximum
number of distinct observations per …

algorithms arxiv monitoring