Exploration by Optimisation in Partial Monitoring

Abstract

We provide a simple and efficient algorithm for adversarial $k$-action $d$-outcome non-degenerate locally observable partial monitoring game for which the $n$-round minimax regret is bounded by $6(d+1)k^{3/2}\sqrt{n\log (k)}$, matching the best known information-theoretic upper bound. The same algorithm also achieves near-optimal regret for full information, bandit and globally observable games.

high probability bounds, experiments and simplified algorithms/analysis