Exploration by Optimisation in Partial Monitoring
This provides an efficient solution for sequential decision-making under partial feedback in adversarial environments, addressing a specific theoretical bottleneck in online learning.
The paper tackles the problem of designing an efficient algorithm for adversarial partial monitoring games with non-degenerate local observability, achieving a minimax regret bound of 6(d+1) k^{3/2} sqrt(n log(k)), which matches the best known upper bound. It also shows near-optimal regret for other game types like full information and bandit games.
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.