Regret Lower Bound and Optimal Algorithm in Finite Stochastic Partial Monitoring
Preprint
Abstract
Partial monitoring is a general model for sequential learning with limited feedback formalized as a game between two players. In this game, the learner chooses an action and at the same time the opponent chooses an outcome, then the learner suffers a loss and receives a feedback signal. The goal of the learner is to minimize the total loss. In this paper, we study partial monitoring with finite actions and stochastic outcomes. We derive a logarithmic distribution-dependent regret lower bound that defines the hardness of the problem. Inspired by the DMED algorithm (Honda and Takemura, 2010) for the multi-armed bandit problem, we propose PM-DMED, an algorithm that minimizes the distribution-dependent regret. PM-DMED significantly outperforms state-of-the-art algorithms in numerical experiments. To show the optimality of PM-DMED with respect to the regret bound, we slightly modify the algorithm by introducing a hinge function (PM-DMED-Hinge). Then, we derive an asymptotically optimal regret upper bound of PM-DMED-Hinge that matches the lower bound.Keywords
All Related Versions
This publication has 7 references indexed in Scilit:
- Regret Minimization Under Partial MonitoringMathematics of Operations Research, 2006
- Minimizing Regret With Label Efficient PredictionIEEE Transactions on Information Theory, 2005
- Finite-time Analysis of the Multiarmed Bandit ProblemMachine Learning, 2002
- A Dual Parametrization Method for Convex Semi-Infinite ProgrammingAnnals of Operations Research, 2000
- Asymptotically Efficient Adaptive Choice of Control Laws inControlled Markov ChainsSIAM Journal on Control and Optimization, 1997
- Asymptotically efficient adaptive allocation rulesAdvances in Applied Mathematics, 1985
- Point-to-Set Maps in Mathematical ProgrammingSIAM Review, 1973