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.

arXiv commenthigh probability bounds, experiments and simplified algorithms/analysis

References in corpus (6)

• Optimization, Learning, and Games with Predictable Sequences
• More Adaptive Algorithms for Adversarial Bandits
• An Information-Theoretic Approach to Minimax Regret in Partial Monitoring
• Beating Stochastic and Adversarial Semi-bandits Optimally and Simultaneously
• Regret Lower Bound and Optimal Algorithm in Finite Stochastic Partial Monitoring
• Connections Between Mirror Descent, Thompson Sampling and the Information Ratio

Cited by in corpus (4)

• Mirror Descent and the Information Ratio
• Information Directed Sampling for Linear Partial Monitoring
• Scale Free Adversarial Multi Armed Bandits
• Matrix games with bandit feedback