An Adaptive Algorithm for Finite Stochastic Partial Monitoring

Abstract

We present a new anytime algorithm that achieves near-optimal regret for any instance of finite stochastic partial monitoring. In particular, the new algorithm achieves the minimax regret, within logarithmic factors, for both "easy" and "hard" problems. For easy problems, it additionally achieves logarithmic individual regret. Most importantly, the algorithm is adaptive in the sense that if the opponent strategy is in an "easy region" of the strategy space then the regret grows as if the problem was easy. As an implication, we show that under some reasonable additional assumptions, the algorithm enjoys an O(\sqrt{T}) regret in Dynamic Pricing, proven to be hard by Bartok et al. (2011).

Appears in Proceedings of the 29th International Conference on Machine Learning (ICML 2012)

References in corpus (1)

• No Internal Regret via Neighborhood Watch

Cited by in corpus (12)

• Cascading Bandits: Learning to Rank in the Cascade Model
• An Information-Theoretic Approach to Minimax Regret in Partial Monitoring
• Combinatorial Cascading Bandits
• Online Influence Maximization under Independent Cascade Model with Semi-Bandit Feedback
• Relative Upper Confidence Bound for the K-Armed Dueling Bandit Problem
• Reducing Dueling Bandits to Cardinal Bandits
• Regret Lower Bound and Optimal Algorithm in Finite Stochastic Partial Monitoring
• Copeland Dueling Bandits
• Information Directed Sampling for Linear Partial Monitoring
• Waterfall Bandits: Learning to Sell Ads Online
• Analysis and Design of Thompson Sampling for Stochastic Partial Monitoring
• Best-of-Both-Worlds Algorithms for Partial Monitoring